A linear-time algorithm for proper interval graph recognition

DOI10.1016/0020-0190(95)00133-WMaRDI QIDQ672268zbMATH OpenOpenAlexFDO

Authors Célia P. de Mello, Celina M. H. 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

zbMATH Keywords

Design of algorithmsIndifference graphsInterval graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A linear time recognition algorithm for proper interval graphs
• scientific article; zbMATH DE number 6810347
• scientific article; zbMATH DE number 4049085
• Recognition of probe proper interval graphs
• scientific article; zbMATH DE number 176590

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 176590 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Clique graphs of time graphs
• On the compatibility between a graph and a simple order
• Simple linear time recognition of unit interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(49)

• Integral mixed unit interval graphs
• scientific article; zbMATH DE number 6810347 (Why is no real title available?)
• Localized and compact data-structure for comparability graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• On the recognition of fuzzy circular interval graphs
• Powers of cycles, powers of paths, and distance graphs
• On-line recognition of interval graphs in \(O(m+n \log n)\) time
• Fully dynamic recognition of proper circular-arc graphs
• Simple linear time recognition of unit interval graphs
• A new representation of proper interval graphs with an application to clique-width
• Decompositions for the edge colouring of reduced indifference graphs.
• FAST EXPONENTIAL-TIME ALGORITHMS FOR THE FOREST COUNTING AND THE TUTTE POLYNOMIAL COMPUTATION IN GRAPH CLASSES
• Graphs of interval count two with a given partition
• Unit and single point interval graphs
• A linear time recognition algorithm for proper interval graphs
• Linear recognition of almost interval graphs
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• Computing the clique-separator graph for an interval graph in linear time
• Proper interval graphs and the guard problem
• scientific article; zbMATH DE number 1303554 (Why is no real title available?)
• The eternal dominating set problem for proper interval graphs
• Simultaneous representation of proper and unit interval graphs
• Exactly hittable interval graphs
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
• Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs
• Recognizing interval bigraphs by forbidden patterns
• Strictly interval graphs: characterization and linear time recognition
• Characterizing interval graphs which are probe unit interval graphs
• Recognition of probe proper interval graphs
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
• On edge-colouring indifference graphs
• Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
• scientific article; zbMATH DE number 176590 (Why is no real title available?)
• Threshold-coloring and unit-cube contact representation of planar graphs
• The Roberts characterization of proper and unit interval graphs
• Semi-proper interval graphs
• Mixed unit interval graphs
• Recognizing and representing proper interval graphs in parallel using merging and sorting
• On partitioning interval graphs into proper interval subgraphs and related problems
• Unit interval graphs: a story with open ends
• A four-sweep LBFS recognition algorithm for interval graphs
• scientific article; zbMATH DE number 4049085 (Why is no real title available?)
• Fully dynamic representations of interval graphs
• Maximum cut on interval graphs of interval count four is NP-complete
• The LBFS structure and recognition of interval graphs
• A Polynomial Time Algorithm for Finding Linear Interval Graph Patterns
• Weak unit disk and interval representation of graphs
• Unit interval graphs of open and closed intervals

This page was built for publication: A linear-time algorithm for proper interval graph recognition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q672268)