A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
type: Item
instance of: scholarly article
title: A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
author: Francisco J. Soulignac
published in: Theoretical Computer Science
publication date: 2021-10-06T00:00:00Z
full work available at URL: https://arxiv.org/abs/1509.05828
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7407474
zbMATH Keywords: dynamic representation
zbMATH Keywords: certifying algorithm
zbMATH Keywords: proper circular-arc graphs
zbMATH Keywords: proper interval graph
zbMATH Keywords: proper Helly circular-arc graphs
MaRDI profile type: Publication
OpenAlex ID: W3189602828
cites work: Algorithmic graph theory and perfect graphs
cites work: Linear time algorithms on circular-arc graphs
cites work: Semiorders. Properties, representations, applications
cites work: Certifying algorithms
cites work: Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
cites work: A Fully dynamic algorithm for recognizing and representing proper interval graphs
cites work: Simple linear time recognition of unit interval graphs
cites work: A linear-time algorithm for proper interval graph recognition
cites work: Fully dynamic recognition of proper circular-arc graphs
cites work: Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
cites work: Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
cites work: A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
cites work: Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
cites work: Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
cites work: Characterizations and recognition of circular-arc graphs and subclasses: a survey
cites work: Fully dynamic recognition algorithm and certificate for directed cographs
cites work: Fully Dynamic Representations of Interval Graphs
cites work: Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
cites work: Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
cites work: Dynamically maintaining split graphs
cites work: Fully dynamic algorithms for chordal graphs and split graphs
cites work: A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
cites work: A fully dynamic graph algorithm for recognizing interval graphs
cites work: A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs
cites work: A fully dynamic algorithm for modular decomposition and recognition of cographs.
cites work: An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs
cites work: On the structure of local tournaments
cites work: Digraphs
cites work: Structure theorems for some circular-arc graphs
cites work: Representation of a finite graph by a set of intervals on the real line
cites work: Normal Helly circular-arc graphs and its subclasses
DOI: 10.1016/J.TCS.2021.07.040
description: scientific article