Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
Pavol Hell, Jing Huang
Source record
Source: Crossref
Published: Jan 1, 2004
DOI: 10.1137/s0895480103430259
Open original source ↗Source abstract
Recently, D. Corneil found a simple 3-sweep lexicographic breadth first search (LexBFS) algorithm for the recognition of proper interval graphs. We point out how to modify Corneil's algorithm to make it a certifying algorithm, and then describe a similar certifying 3-sweep LexBFS algorithm for the recognition of proper interval bigraphs. It follows from an earlier paper that the class of proper interval bigraphs is equal to the better known class of bipartite permutation graphs, and so we have a certifying algorithm for that class as well. All our algorithms run in time O(m+n), including the certification phase. The certificates of representability (the intervals) can be authenticated in time O(m+n). The certificates of nonrepresentability (the forbidden subgraphs) can be authenticated in time O(n).
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.