Fully dynamic representations of interval graphs

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem
A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs
A linear-time algorithm for proper interval graph recognition
Simple linear time recognition of unit interval graphs
Minimal triangulations of graphs: a survey
A linear time recognition algorithm for proper interval graphs
Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
Efficient graph representations
PC trees and circular-ones arrangements.
A fully dynamic algorithm for modular decomposition and recognition of cographs.
Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
Algorithmic graph theory and perfect graphs
A fully dynamic graph algorithm for recognizing interval graphs
Fast algorithms to enumerate all common intervals of two permutations
Fully dynamic recognition algorithm and certificate for directed cographs
A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of Graphs
Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs
A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
Incremental modular decomposition
An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
Separator-Based Sparsification II: Edge and Vertex Connectivity
Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
Graph Classes: A Survey
On-Line Planarity Testing
Fully dynamic algorithms for chordal graphs and split graphs
Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
The complexity of theorem-proving procedures
A Characterization of Comparability Graphs and of Interval Graphs
Fully Dynamic Representations of Interval Graphs
Graph-Theoretic Concepts in Computer Science
Algorithms and Computation
Fully dynamic algorithm for recognition and modular decomposition of permutation graphs

This page was built for publication: Fully dynamic representations of interval graphs