Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
Authors:
- Dieter KratschDKDieter Kratsch
- Ross M. McConnellRMRoss M. McConnell
- Kurt MehlhornKMKurt Mehlhorn
- Jeremy P. SpinradJSJeremy P. Spinrad
- 1 January 2006
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 36 (2) , 326-353
Abstract
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 linear-time certifying algorithms for recognition of interval graphs and permutation graphs, and for a few other related problems. 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 nonmembership can be authenticated in O(|V|) time.Keywords
This publication has 23 references indexed in Scilit:
- PC trees and circular-ones arrangementsTheoretical Computer Science, 2003
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testingTheoretical Computer Science, 2000
- Graph Classes: A Survey1999
- An Incremental Linear-Time Algorithm for Recognizing Interval GraphsSIAM Journal on Computing, 1989
- A Linear Recognition Algorithm for CographsSIAM Journal on Computing, 1985
- Fast Algorithms for Finding Nearest Common AncestorsSIAM Journal on Computing, 1984
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithmsJournal of Computer and System Sciences, 1976
- Transitiv orientierbare GraphenActa Mathematica Hungarica, 1967
- Representation of a finite graph by a set of intervals on the real lineFundamenta Mathematicae, 1962
- On rigid circuit graphsAbhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, 1961