Fully Dynamic Representations of Interval Graphs

DOI10.1007/978-3-642-11409-0_7zbMath1273.05150OpenAlexW1600202620MaRDI QIDQ5851095

Christophe Crespelle

Publication date: 21 January 2010

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-00644222/file/S0304397519300209.pdf

zbMATH Keywords

maximal cliquesinterval graphmodular decompositiongraph representationsedge modificationminimal interval modelvertex modification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (7)

An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ A fully dynamic algorithm for the recognition of \(P_4\)-sparse graphs ⋮ Fully dynamic representations of interval graphs ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ Fully dynamic recognition of proper circular-arc graphs

This page was built for publication: Fully Dynamic Representations of Interval Graphs