An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
From MaRDI portal
Publication:3835023
Recommendations
Cited in
(65)- An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem
- Normal Helly circular-arc graphs and its subclasses
- Reconfiguration of Steiner trees in an unweighted graph
- Minimal obstructions for partial representations of interval graphs
- Cops, a fast robber and defensive domination on interval graphs
- Counting endpoint sequences for interval orders and interval graphs
- Satisfiability problems on intervals and unit intervals
- Reconfiguration of Minimum Steiner Trees via Vertex Exchanges
- A faster algorithm for finding minimum Tucker submatrices
- Reconstruction of Interval Graphs
- On-line recognition of interval graphs in O(m+n n) time
- Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
- Weighted irredundance of interval graphs.
- Simple linear time recognition of unit interval graphs
- A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
- Simpler and unified recognition algorithm for path graphs and directed path graphs
- On probe interval graphs
- A linear time recognition algorithm for proper interval graphs
- Linear recognition of almost interval graphs
- A linear-time algorithm for the weighted feedback vertex problem on interval graphs
- A simple algorithm to find Hamiltonian cycles in proper interval graphs
- Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
- Periodic assignment and graph colouring
- Computing the clique-separator graph for an interval graph in linear time
- On the classes of interval graphs of limited nesting and count of lengths
- scientific article; zbMATH DE number 1303554 (Why is no real title available?)
- MPQ-trees for orthogonal packing problem
- A polynomial-time algorithm for finding a minimal conflicting set containing a given row
- On computing longest paths in small graph classes
- A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Enumeration and maximum number of maximal irredundant sets for chordal graphs
- Reconstruction of interval graphs
- Recognizing interval bigraphs by forbidden patterns
- On the interval completion of chordal graphs
- Dynamically maintaining split graphs
- Partition refinement techniques: an interesting algorithmic tool kit
- BOB: Improved winner determination in combinatorial auctions and generalizations
- Scale free interval graphs
- scientific article; zbMATH DE number 176590 (Why is no real title available?)
- Graph isomorphism restricted by lists
- Interval graphs with side (and size) constraints
- A fully dynamic graph algorithm for recognizing interval graphs
- ILIGRA: an efficient inverse line graph algorithm
- Semi-proper interval graphs
- A linear-time algorithm for proper interval graph recognition
- Coloring mixed and directional interval graphs
- Shortest reconfiguration of sliding tokens on subclasses of interval graphs
- Enumeration of nonisomorphic interval graphs and nonisomorphic permutation graphs
- A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
- Induced disjoint paths in circular-arc graphs in linear time
- On minimum intersection of two minimum dominating sets of interval graphs
- MPQ-trees for the orthogonal packing problem
- Weighted independent perfect domination on cocomparability graphs
- Chronological rectangle digraphs which are two-terminal series-parallel
- scientific article; zbMATH DE number 4049085 (Why is no real title available?)
- Catching a fast robber on interval graphs
- Recognizing d-interval graphs and d-track interval graphs
- Minimal obstructions for partial representations of interval graphs
- PC trees and circular-ones arrangements.
- Strict chordal and strict split digraphs
- Fully dynamic representations of interval graphs
- A note on lexicographic breadth first search for chordal graphs
- A Polynomial Time Algorithm for Finding Linear Interval Graph Patterns
- Shortest Reconfiguration of Sliding Tokens on a Caterpillar
This page was built for publication: An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3835023)
