Fully dynamic recognition of proper circular-arc graphs
From MaRDI portal
Publication:2350902
DOI10.1007/s00453-013-9835-7zbMath1323.05125arXiv1111.3548OpenAlexW3098447893MaRDI QIDQ2350902
Publication date: 25 June 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1111.3548
minimal forbidden induced subgraphsproper circular-arc graphsdynamic recognitionco-connectivityround graphs
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (6)
Solving the canonical representation and star system problems for proper circular-arc graphs in logspace ⋮ Essential obstacles to Helly circular-arc graphs ⋮ Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs ⋮ Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ Circular-arc hypergraphs: rigidity via connectedness
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- A fully dynamic algorithm for modular decomposition and recognition of cographs.
- A simple 3-sweep LBFS algorithm for the recognition of unit interval 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 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
- A Fully Dynamic Algorithm for Recognizing and Representing Chordal Graphs
- A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc 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
- Fully Dynamic Representations of Interval Graphs
- Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
This page was built for publication: Fully dynamic recognition of proper circular-arc graphs
