Dieter Kratsch
Kurt Mehlhorn
ABSTRACT
A certifying algorithm for a decision problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence that proves that the answer has not been compromised by a bug in the implementation. We give linear-time certifying algorithms for recognition of interval graphs and permutation graphs. Previous algorithms fail to provide supporting evidence when they claim that the input graph is not a member of the class. We show that our certificates of non-membership can be authenticated in O(|V|) time.
Index Terms
- Certifying algorithms for recognizing interval graphs and permutation graphs
Recommendations
Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence that proves that the answer has not been compromised by a bug in the implementation. We give ...
Constant factor approximation algorithms for the densest k-subgraph problem on proper interval graphs and bipartite permutation graphs
The densest k-subgraph problem asks for a k-vertex subgraph with the maximum number of edges. This problem is NP-hard on bipartite graphs, chordal graphs, and planar graphs. A 3-approximation algorithm is known for chordal graphs. We present 32-...
Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
In this paper, we present a linear-time algorithm for substitution decomposition on chordal graphs. Based on this result, we develop a linear-time algorithm for transitive orientation on chordal comparability graphs, which reduces the complexity of ...
Comments