Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
From MaRDI portal
Publication:3434989
Recommendations
- scientific article; zbMATH DE number 2079335
- Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
- Certifying algorithms
- Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
- Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
Cited in
(39)- Distributed interactive proofs for the recognition of some geometric intersection graph classes
- Minimal comparability completions of arbitrary graphs
- Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
- Certifying algorithms
- Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
- Linear-time certifying recognition algorithms and forbidden induced subgraphs
- Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
- Recognition and characterization of unit interval graphs with integer endpoints
- Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection
- Algorithms and complexity of \(s\)-club cluster vertex deletion
- Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
- Construction sequences and certifying 3-connectivity
- Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
- A simple certifying algorithm for 3-edge-connectivity
- Counting independent sets in cocomparability graphs
- On the power of graph searching for cocomparability graphs
- Essential obstacles to Helly circular-arc graphs
- Recognition of split-graphic sequences
- A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
- Permutation bigraphs and interval containments
- Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge
- Maximizing the strong triadic closure in split graphs and proper interval graphs
- An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
- Recognizing stick graphs with and without length constraints
- An \(O(nm)\)-time certifying algorithm for recognizing HHD-free graphs
- Stick graphs with length constraints
- On graphs associated to sets of rankings
- Fully dynamic representations of interval graphs
- Certifying coloring algorithms for graphs without long induced paths
- A linear-time certifying algorithm for recognizing generalized series-parallel graphs
- Progress on certifying algorithms
- On unit interval graphs with integer endpoints
- Uniquely restricted matchings in interval graphs
- A polynomial-time algorithm for the paired-domination problem on permutation graphs
- Certifying induced subgraphs in large graphs
- Comparing series of rankings with ties by using complex networks: an analysis of the Spanish stock market (IBEX-35 index)
- Fast algorithms for the undirected negative cost cycle detection problem
- Normal Helly circular-arc graphs and its subclasses
- List matrix partitions of graphs representing geometric configurations
This page was built for publication: Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3434989)
