A linear-time algorithm for proper interval graph recognition
From MaRDI portal
Publication:672268
DOI10.1016/0020-0190(95)00133-WzbMath0875.68696OpenAlexW2063909168MaRDI QIDQ672268
Célia Picinin de Mello, Celina M. Herrera de Figueiredo, João Meidanis
Publication date: 28 February 1997
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(95)00133-w
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (28)
Proper interval graphs and the guard problem ⋮ Threshold-coloring and unit-cube contact representation of planar graphs ⋮ Characterizing interval graphs which are probe unit interval graphs ⋮ On edge-colouring indifference graphs ⋮ Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs ⋮ On the recognition of fuzzy circular interval graphs ⋮ Maximum cut on interval graphs of interval count four is NP-complete ⋮ Decompositions for the edge colouring of reduced indifference graphs. ⋮ Unit and single point interval graphs ⋮ Integral mixed unit interval graphs ⋮ Fully dynamic representations of interval graphs ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ The Roberts characterization of proper and unit interval graphs ⋮ Unit Interval Graphs of Open and Closed Intervals ⋮ Powers of cycles, powers of paths, and distance graphs ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Graphs of interval count two with a given partition ⋮ Mixed unit interval graphs ⋮ A Lex-BFS-based recognition algorithm for Robinsonian matrices ⋮ FAST EXPONENTIAL-TIME ALGORITHMS FOR THE FOREST COUNTING AND THE TUTTE POLYNOMIAL COMPUTATION IN GRAPH CLASSES ⋮ Localized and compact data-structure for comparability graphs ⋮ Weak Unit Disk and Interval Representation of Graphs ⋮ A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs ⋮ A new representation of proper interval graphs with an application to clique-width ⋮ The eternal dominating set problem for proper interval graphs ⋮ Fully dynamic recognition of proper circular-arc graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Simple linear time recognition of unit interval graphs
- Clique graphs of time graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- On the compatibility between a graph and a simple order
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- A Characterization of Comparability Graphs and of Interval Graphs
This page was built for publication: A linear-time algorithm for proper interval graph recognition
