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

DOI10.1016/J.TCS.2021.07.040OpenAlexW3189602828MaRDI QIDQ2232611FDOQ2232611

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

Cited In (6)

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