Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
From MaRDI portal
Publication:3434989
DOI10.1137/S0097539703437855zbMath1113.68112MaRDI QIDQ3434989
Kurt Mehlhorn, Dieter Kratsch, Ross M. McConnell, Jeremy P. Spinrad
Publication date: 3 May 2007
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)
Related Items (36)
On unit interval graphs with integer endpoints ⋮ Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs ⋮ Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection ⋮ Essential obstacles to Helly circular-arc graphs ⋮ Certifying coloring algorithms for graphs without long induced paths ⋮ Permutation bigraphs and interval containments ⋮ Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs ⋮ Maximizing the strong triadic closure in split graphs and proper interval graphs ⋮ Construction sequences and certifying 3-connectivity ⋮ A simple certifying algorithm for 3-edge-connectivity ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ Stick graphs with length constraints ⋮ A new graph parameter to measure linearity ⋮ Fully dynamic representations of interval graphs ⋮ Counting independent sets in cocomparability graphs ⋮ Certifying algorithms ⋮ Recognizing Stick Graphs with and without Length Constraints ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ On graphs associated to sets of rankings ⋮ List matrix partitions of graphs representing geometric configurations ⋮ Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge ⋮ Recognition and characterization of unit interval graphs with integer endpoints ⋮ Minimal comparability completions of arbitrary graphs ⋮ Recognition of split-graphic sequences ⋮ Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs ⋮ Approximation and fixed-parameter algorithms for consecutive ones submatrix problems ⋮ An \(O(nm)\)-time certifying algorithm for recognizing HHD-free graphs ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs ⋮ On the Power of Graph Searching for Cocomparability Graphs ⋮ A polynomial-time algorithm for the paired-domination problem on permutation graphs ⋮ Distributed interactive proofs for the recognition of some geometric intersection graph classes ⋮ Uniquely Restricted Matchings in Interval Graphs ⋮ A linear-time certifying algorithm for recognizing generalized series-parallel graphs ⋮ Algorithms and complexity of \(s\)-club cluster vertex deletion ⋮ 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
This page was built for publication: Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
