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

DOI10.1016/j.dam.2009.07.002zbMath1213.05248OpenAlexW2022376879MaRDI QIDQ967378

Yahav Nussbaum, Haim Kaplan

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)

Related Items (14)

On a Verification Framework for Certifying Distributed Algorithms: Distributed Checking and Consistency ⋮ Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection ⋮ Solving the canonical representation and star system problems for proper circular-arc graphs in logspace ⋮ Essential obstacles to Helly circular-arc graphs ⋮ Analyzing read-once cutting plane proofs in Horn systems ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory ⋮ Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter II: algorithms ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ Circular-arc hypergraphs: rigidity via connectedness ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs ⋮ On the lengths of tree-like and dag-like cutting plane refutations of Horn constraint systems. Horn constraint systems and cutting plane refutations ⋮ Fully dynamic recognition of proper circular-arc graphs ⋮ On the isomorphism problem for Helly circular-arc graphs

Uses Software

• LEDA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of comparability graph recognition and coloring
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Recognizing interval digraphs and interval bigraphs in polynomial time
• Efficient graph representations
• PC trees and circular-ones arrangements.
• Linear-time recognition of circular-arc graphs
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• Matrix characterizations of circular-arc graphs
• Structure theorems for some 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
• Unit Circular-Arc Graph Representations and Feasible Circulations
• Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs
• Algorithms on circular-arc graphs
• Graph Classes: A Survey
• Interval bigraphs and circular arc graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
• Polynomial time recognition of unit circular-arc graphs
• A Simpler Linear-Time Recognition of Circular-Arc Graphs

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