A linear time recognition algorithm for proper interval graphs
From MaRDI portal
Publication:1014413
DOI10.1016/S0020-0190(03)00298-9zbMath1161.68855MaRDI QIDQ1014413
Publication date: 28 April 2009
Published in: Information Processing Letters (Search for Journal in Brave)
Related Items (43)
Acyclic Matching in Some Subclasses of Graphs ⋮ Complexity of Hamiltonian cycle reconfiguration ⋮ Algorithmic Aspects of Disjunctive Domination in Graphs ⋮ Hamiltonian paths, unit-interval complexes, and determinantal facet ideals ⋮ Injective coloring of some subclasses of bipartite graphs and chordal graphs ⋮ Exact square coloring of certain classes of graphs: complexity and algorithms ⋮ The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy ⋮ Unique response Roman domination: complexity and algorithms ⋮ On the recognition of fuzzy circular interval graphs ⋮ Acyclic matching in some subclasses of graphs ⋮ Minimum maximal acyclic matching in proper interval graphs ⋮ 2-Trees: Structural insights and the study of Hamiltonian paths ⋮ An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs ⋮ Algorithms and hardness results for edge total domination problem in graphs ⋮ Algorithm and hardness results on neighborhood total domination in graphs ⋮ Fully dynamic representations of interval graphs ⋮ Computing a minimum outer-connected dominating set for the class of chordal graphs ⋮ A linear time algorithm for liar's domination problem in proper interval graphs ⋮ On some inverse 1-center location problems ⋮ The Roberts characterization of proper and unit interval graphs ⋮ Template-driven rainbow coloring of proper interval graphs ⋮ Star Partitions of Perfect Graphs ⋮ Minimal proper interval completions ⋮ Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs ⋮ Template-driven rainbow coloring of proper interval graphs ⋮ A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs ⋮ A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs ⋮ A simple algorithm to find Hamiltonian cycles in proper interval graphs ⋮ Measuring Indifference: Unit Interval Vertex Deletion ⋮ Algorithmic aspects of \(b\)-disjunctive domination in graphs ⋮ Random Generation and Enumeration of Proper Interval Graphs ⋮ Algorithmic aspects of upper paired-domination in graphs ⋮ Complexity of Steiner Tree in Split Graphs - Dichotomy Results ⋮ ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES ⋮ The strong domination problem in block graphs and proper interval graphs ⋮ On the complexity of minimum maximal uniquely restricted matching ⋮ Algorithmic results on double Roman domination in graphs ⋮ Double vertex-edge domination in graphs: complexity and algorithms ⋮ 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 ⋮ Mathematical properties on the hyperbolicity of interval graphs ⋮ Perfect Roman domination in graphs ⋮ A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Simple linear time recognition of unit interval graphs
- Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs
- On rigid circuit graphs
- Finding Hamiltonian cycles in certain planar graphs
- Finding Hamiltonian circuits in proper interval graphs
- Finding Hamiltonian circuits in interval graphs
- Hamiltonian circuits in interval graph generalizations
- The edge Hamiltonian path problem is NP-complete
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The Scott-Suppes theorem on semiorders
- Clique tree generalization and new subclasses of chordal graphs
- Intersection graphs of vertex disjoint paths in a tree
- Incidence matrices and interval graphs
- On the Desirability of Acyclic Database Schemes
- Foundational aspects of theories of measurement
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- Scheduling Interval-Ordered Tasks
- The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs
- An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Hamilton Paths in Grid Graphs
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- A Characterization of Comparability Graphs and of Interval Graphs
This page was built for publication: A linear time recognition algorithm for proper interval graphs
