A linear time recognition algorithm for proper interval graphs
From MaRDI portal
Recommendations
- A linear-time algorithm for proper interval graph recognition
- scientific article; zbMATH DE number 4049085
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- scientific article; zbMATH DE number 176590
- Strictly interval graphs: characterization and linear time recognition
- Simple linear time recognition of unit interval graphs
- A polynomial time recognition algorithm for probe interval graphs
- A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
Cites work
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 4152428 (Why is no real title available?)
- scientific article; zbMATH DE number 3706451 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 512914 (Why is no real title available?)
- A Characterization of Comparability Graphs and of Interval Graphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- Clique tree generalization and new subclasses of chordal graphs
- Finding Hamiltonian circuits in interval graphs
- Finding Hamiltonian circuits in proper interval graphs
- Finding Hamiltonian cycles in certain planar graphs
- Foundational aspects of theories of measurement
- Hamilton Paths in Grid Graphs
- Hamiltonian circuits in interval graph generalizations
- Incidence matrices and interval graphs
- Intersection graphs of vertex disjoint paths in a tree
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- On rigid circuit graphs
- On the Desirability of Acyclic Database Schemes
- Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs
- Scheduling Interval-Ordered Tasks
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Simple linear time recognition of unit interval graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs
- The Planar Hamiltonian Circuit Problem is NP-Complete
- The Scott-Suppes theorem on semiorders
- The edge Hamiltonian path problem is NP-complete
Cited in
(54)- Semi-proper interval graphs
- Algorithms and hardness results for edge total domination problem in 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
- The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy
- Double vertex-edge domination in graphs: complexity and algorithms
- Minimal proper interval completions
- scientific article; zbMATH DE number 1303554 (Why is no real title available?)
- Acyclic matching in some subclasses of graphs
- Exact square coloring of certain classes of graphs: complexity and algorithms
- Computing a minimum outer-connected dominating set for the class of chordal graphs
- A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
- Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
- The strong domination problem in block graphs and proper interval graphs
- Algorithmic aspects of upper paired-domination in graphs
- scientific article; zbMATH DE number 1955841 (Why is no real title available?)
- On the complexity of minimum maximal uniquely restricted matching
- Algorithm and hardness results on neighborhood total domination in graphs
- On some inverse 1-center location problems
- Unique response Roman domination: complexity and algorithms
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- A new representation of proper interval graphs with an application to clique-width
- On the recognition of fuzzy circular interval graphs
- A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs
- A linear-time algorithm for proper interval graph recognition
- Template-driven rainbow coloring of proper interval graphs
- Random Generation and Enumeration of Proper Interval Graphs
- Complexity of Hamiltonian cycle reconfiguration
- Complexity of Steiner tree in split graphs -- dichotomy results
- A Polynomial Time Algorithm for Finding Linear Interval Graph Patterns
- Recognizing and representing proper interval graphs in parallel using merging and sorting
- Algorithmic aspects of \(b\)-disjunctive domination in graphs
- Fully dynamic representations of interval graphs
- scientific article; zbMATH DE number 6810347 (Why is no real title available?)
- Algorithmic results on double Roman domination in graphs
- Acyclic Matching in Some Subclasses of Graphs
- The Roberts characterization of proper and unit interval graphs
- Perfect Roman domination in graphs
- Strictly interval graphs: characterization and linear time recognition
- A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
- Template-driven rainbow coloring of proper interval graphs
- Minimum maximal acyclic matching in proper interval graphs
- Mathematical properties on the hyperbolicity of interval graphs
- Measuring indifference: unit interval vertex deletion
- A linear time algorithm for liar's domination problem in proper interval graphs
- On computing longest paths in small graph classes
- A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs
- A simple algorithm to find Hamiltonian cycles in proper interval graphs
- Injective coloring of some subclasses of bipartite graphs and chordal graphs
- Simple linear time recognition of unit interval graphs
- Hamiltonian paths, unit-interval complexes, and determinantal facet ideals
- Algorithmic aspects of disjunctive domination in graphs
- Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
This page was built for publication: A linear time recognition algorithm for proper interval graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1014413)
