A fully dynamic graph algorithm for recognizing interval graphs
From MaRDI portal
Publication:1957648
DOI10.1007/s00453-009-9291-6zbMath1200.05227OpenAlexW2136895095MaRDI QIDQ1957648
Publication date: 27 September 2010
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-009-9291-6
Related Items (5)
Computing the clique-separator graph for an interval graph in linear time ⋮ Backup 2-center on interval graphs ⋮ Fully dynamic representations of interval graphs ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ Fully dynamic recognition of proper circular-arc graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Simple linear time recognition of unit interval graphs
- The clique-separator graph for chordal graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Counting clique trees and computing perfect elimination schemes in parallel
- Algorithmic graph theory and perfect graphs
- Incidence matrices and interval graphs
- A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
- The NP-completeness column: an ongoing guide
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- Efficiency of a Good But Not Linear Set Union Algorithm
- Algorithmic Aspects of Vertex Elimination on Graphs
- Separator-Based Sparsification II: Edge and Vertex Connectivity
- Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
- Topics in Intersection Graph Theory
- Graph Classes: A Survey
- Sparsification—a technique for speeding up dynamic graph algorithms
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Fully dynamic algorithms for chordal graphs and split graphs
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
This page was built for publication: A fully dynamic graph algorithm for recognizing interval graphs
