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

DOI10.1016/J.TCS.2021.07.040MaRDI QIDQ2232611zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Fully dynamic recognition of proper circular-arc graphs
• A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs

Cites work

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

Cited in

(6)

• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
• A Simpler Linear-Time Recognition of Circular-Arc Graphs
• A dynamic distributed approach to representing proper interval graphs
• Fully dynamic recognition of proper circular-arc graphs
• Direct and Certifying Recognition of Normal Helly Circular-Arc Graphs in Linear Time
• Linear-time recognition of circular-arc graphs

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

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