Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs

DOI10.1016/J.DAM.2009.07.002MaRDI QIDQ967378zbMATH OpenOpenAlexFDO

Authors Haim Kaplan, Yahav Nussbaum

Publication date 28 April 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2009.07.002

zbMATH Keywords

certifying algorithmgraph recognitionproper circular-arcunit circular-arc

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
• A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
• Polynomial time recognition of unit circular-arc graphs
• scientific article; zbMATH DE number 437537
• Linear-time recognition of circular-arc graphs
• A simpler linear-time recognition of circular-arc graphs
• A Simpler Linear-Time Recognition of Circular-Arc Graphs
• Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
• Direct and Certifying Recognition of Normal Helly Circular-Arc Graphs in Linear Time
• Fully dynamic recognition of proper circular-arc graphs

Cites work

• scientific article; zbMATH DE number 1368469 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A Simpler Linear-Time Recognition of Circular-Arc Graphs
• A certifying algorithm for the consecutive-ones property
• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
• Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Algorithms on circular-arc graphs
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
• Efficient graph representations
• Graph Classes: A Survey
• Interval bigraphs and circular arc graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Linear-time recognition of circular-arc graphs
• Matrix characterizations of circular-arc graphs
• PC trees and circular-ones arrangements.
• Polynomial time recognition of unit circular-arc graphs
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Structure theorems for some circular-arc graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The complexity of comparability graph recognition and coloring
• Unit Circular-Arc Graph Representations and Feasible Circulations

Cited in

(23)

• On the lengths of tree-like and dag-like cutting plane refutations of Horn constraint systems. Horn constraint systems and cutting plane refutations
• Unit Circular-Arc Graph Representations and Feasible Circulations
• On a Verification Framework for Certifying Distributed Algorithms: Distributed Checking and Consistency
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• scientific article; zbMATH DE number 2079335 (Why is no real title available?)
• A polynomial kernel for proper Helly circular-arc vertex deletion
• Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
• Essential obstacles to Helly circular-arc graphs
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. I: Theory
• A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
• Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
• Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
• Fully dynamic recognition of proper circular-arc graphs
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. II: Algorithms
• Polynomial time recognition of unit circular-arc graphs
• An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs
• Direct and Certifying Recognition of Normal Helly Circular-Arc Graphs in Linear Time
• Circular-arc hypergraphs: rigidity via connectedness
• On the isomorphism problem for Helly circular-arc graphs
• Analyzing read-once cutting plane proofs in Horn systems
• Normal Helly circular-arc graphs and its subclasses

Describes a project that uses

Uses Software

• LEDA

This page was built for publication: Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q967378)