A certifying and dynamic algorithm for the recognition of proper circular-arc graphs

DOI10.1016/j.tcs.2021.07.040OpenAlexW3189602828MaRDI QIDQ2232611

Francisco J. Soulignac

Publication date: 6 October 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1509.05828

zbMATH Keywords

proper interval graphcertifying algorithmproper circular-arc graphsdynamic representationproper Helly circular-arc graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs
• Certifying algorithms
• A linear-time algorithm for proper interval graph recognition
• Simple linear time recognition of unit interval graphs
• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
• Dynamically maintaining split graphs
• Characterizations and recognition of circular-arc graphs and subclasses: a survey
• Linear time algorithms on circular-arc graphs
• Semiorders. Properties, representations, applications
• A fully dynamic algorithm for modular decomposition and recognition of cographs.
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Algorithmic graph theory and perfect graphs
• On the structure of local tournaments
• Normal Helly circular-arc graphs and its subclasses
• A fully dynamic graph algorithm for recognizing interval graphs
• Fully dynamic recognition of proper circular-arc graphs
• Fully dynamic recognition algorithm and certificate for directed cographs
• Structure theorems for some circular-arc graphs
• A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
• Representation of a finite graph by a set of intervals on the real line
• Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
• An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs
• A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Fully dynamic algorithms for chordal graphs and split graphs
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
• Digraphs
• Fully Dynamic Representations of Interval Graphs
• Fully dynamic algorithm for recognition and modular decomposition of permutation graphs

This page was built for publication: A certifying and dynamic algorithm for the recognition of proper circular-arc graphs