A linear-time algorithm for proper interval graph recognition

DOI10.1016/0020-0190(95)00133-WzbMATH Open0875.68696OpenAlexW2063909168MaRDI QIDQ672268FDOQ672268

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

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 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)

Cites Work

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Simple linear time recognition of unit interval graphs
• A Characterization of Comparability Graphs and of Interval Graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Clique graphs of time graphs
• Title not available (Why is that?)

Cited In (44)

• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Localized and compact data-structure for comparability graphs
• On the recognition of fuzzy circular interval graphs
• Powers of cycles, powers of paths, and distance graphs
• A new representation of proper interval graphs with an application to clique-width
• Fully dynamic recognition of proper circular-arc graphs
• Simple linear time recognition of unit interval graphs
• 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
• Weak Unit Disk and Interval Representation of Graphs
• Graphs of interval count two with a given partition
• Unit and single point interval graphs
• A linear time recognition algorithm for proper interval graphs
• A Lex-BFS-based recognition algorithm for Robinsonian matrices
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• Title not available (Why is that?)
• Proper interval graphs and the guard problem
• Exactly hittable interval graphs
• The eternal dominating set problem for proper 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
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
• Characterizing interval graphs which are probe unit interval graphs
• On edge-colouring indifference graphs
• Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
• Title not available (Why is that?)
• Threshold-coloring and unit-cube contact representation of planar graphs
• The Roberts characterization of proper and unit 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Unit interval graphs of open and closed intervals
• Title not available (Why is that?)
• Integral mixed unit interval graphs
• Linear-Time Recognition of Probe Interval Graphs

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)