Fully dynamic representations of interval graphs
type: Item
instance of: scholarly article
title: Fully dynamic representations of interval graphs
zbMATH Open document ID: 1403.68158
author: Christophe Crespelle
published in: Theoretical Computer Science
publication date: 2019-01-18T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7003518
zbMATH Keywords: interval graphs
zbMATH Keywords: dynamic algorithms
zbMATH Keywords: PQ-tree
zbMATH Keywords: modular decomposition
MaRDI profile type: Publication
cites work: Fully Dynamic Representations of Interval Graphs
cites work: The complexity of theorem-proving procedures
cites work: Graph Classes: A Survey
cites work: Algorithmic graph theory and perfect graphs
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: Q4250178
cites work: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
cites work: Q4281626
cites work: Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
cites work: An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
cites work: Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
cites work: Q3686754
cites work: Q4035766
cites work: A simple 3-sweep LBFS algorithm for the recognition of unit 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: Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
cites work: A linear time recognition algorithm for proper interval graphs
cites work: Efficient graph representations
cites work: An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem
cites work: On-Line Planarity Testing
cites work: Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
cites work: Fully dynamic recognition algorithm and certificate for directed cographs
cites work: Separator-Based Sparsification II: Edge and Vertex Connectivity
cites work: A Fully dynamic algorithm for recognizing and representing proper interval graphs
cites work: Fully dynamic algorithms for chordal graphs and split 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: A fully dynamic graph algorithm for recognizing interval graphs
cites work: A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
cites work: Incremental modular decomposition
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of Graphs
cites work: Algorithms and Computation
cites work: Fast algorithms to enumerate all common intervals of two permutations
cites work: A Characterization of Comparability Graphs and of Interval Graphs
cites work: Q3683903
cites work: PC trees and circular-ones arrangements.
cites work: Minimal triangulations of graphs: a survey
Wikidata QID: Q128632383
DOI: 10.1016/J.TCS.2019.01.007
Recommended article: Fully Dynamic Representations of Interval Graphs
Recommended article: A Fully dynamic algorithm for recognizing and representing proper interval graphs
Recommended article: A fully dynamic graph algorithm for recognizing interval graphs
Recommended article: A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
Recommended article: On interval representations of graphs
Recommended article: A dynamic distributed approach to representing proper interval graphs
Recommended article: Extending partial representations of interval graphs
Recommended article: Interval representations of planar graphs
Recommended article: A practical succinct dynamic graph representation
description: scientific article; zbMATH DE number 7003518