An Incremental Linear-Time Algorithm for Recognizing Interval Graphs

DOI10.1137/0218005zbMath0678.68043OpenAlexW2057556050MaRDI QIDQ3835023

Norbert Korte, Rolf H. Möhring

Publication date: 1989

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0218005

zbMATH Keywords

graph algorithminterval graphsincremental recognitionperfect elimination schemeamortized timemodified PQ-tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (56)

MPQ-trees for orthogonal packing problem ⋮ Periodic assignment and graph colouring ⋮ A linear-time algorithm for the weighted feedback vertex problem on interval graphs ⋮ Computing the clique-separator graph for an interval graph in linear time ⋮ Induced disjoint paths in circular-arc graphs in linear time ⋮ Reconstruction of Interval Graphs ⋮ Shortest reconfiguration of sliding tokens on subclasses of interval graphs ⋮ Weighted independent perfect domination on cocomparability graphs ⋮ On minimum intersection of two minimum dominating sets of interval graphs ⋮ Reconstruction of interval graphs ⋮ Extending partial representations of interval graphs ⋮ Minimal Obstructions for Partial Representations of Interval Graphs ⋮ An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem ⋮ Chronological rectangle digraphs which are two-terminal series-parallel ⋮ Satisfiability problems on intervals and unit intervals ⋮ MPQ-trees for the orthogonal packing problem ⋮ Recognizing interval bigraphs by forbidden patterns ⋮ Interval graphs with side (and size) constraints ⋮ PC trees and circular-ones arrangements. ⋮ Coloring mixed and directional interval graphs ⋮ A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ Fully dynamic representations of interval graphs ⋮ A fully dynamic graph algorithm for recognizing interval graphs ⋮ Minimal obstructions for partial representations of interval graphs ⋮ On the classes of interval graphs of limited nesting and count of lengths ⋮ A linear-time algorithm for proper interval graph recognition ⋮ Simple linear time recognition of unit interval graphs ⋮ A note on lexicographic breadth first search for chordal graphs ⋮ A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row ⋮ Catching a Fast Robber on Interval Graphs ⋮ Strict chordal and strict split digraphs ⋮ Counting endpoint sequences for interval orders and interval graphs ⋮ A faster algorithm for finding minimum Tucker submatrices ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ Approximation and fixed-parameter algorithms for consecutive ones submatrix problems ⋮ On the interval completion of chordal graphs ⋮ A simple algorithm to find Hamiltonian cycles in proper interval graphs ⋮ A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs ⋮ Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs ⋮ Enumeration and maximum number of maximal irredundant sets for chordal graphs ⋮ ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES ⋮ Graph isomorphism restricted by lists ⋮ Shortest Reconfiguration of Sliding Tokens on a Caterpillar ⋮ A linear time recognition algorithm for proper interval graphs ⋮ Reconfiguration of Steiner Trees in an Unweighted Graph ⋮ Dynamically maintaining split graphs ⋮ Reconfiguration of Minimum Steiner Trees via Vertex Exchanges ⋮ On probe interval graphs ⋮ A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs ⋮ Scale free interval graphs ⋮ Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing ⋮ Cops, a fast robber and defensive domination on interval graphs ⋮ PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT ⋮ Weighted irredundance of interval graphs. ⋮ BOB: Improved winner determination in combinatorial auctions and generalizations

This page was built for publication: An Incremental Linear-Time Algorithm for Recognizing Interval Graphs