Fully dynamic representations of interval graphs

DOI10.1016/J.TCS.2019.01.007MaRDI QIDQ1711837zbMATH OpenWikidataFDO

Authors Christophe Crespelle

Publication date 18 January 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

interval graphsmodular decompositiondynamic algorithmsPQ-tree

Mathematics Subject Classification ID

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

Recommendations

• Fully dynamic representations of interval graphs
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• A fully dynamic graph algorithm for recognizing interval graphs
• A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
• On interval representations of graphs
• A dynamic distributed approach to representing proper interval graphs
• Interval representations of planar graphs
• A practical succinct dynamic graph representation

Cites work

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

Cited in

(7)

• Graph-Theoretic Concepts in Computer Science
• Modules and PQ-trees in Robinson spaces
• Distance queries over dynamic interval graphs
• Fully dynamic representations of interval graphs
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• A fully dynamic graph algorithm for recognizing interval graphs
• Distance queries over dynamic interval graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1711837)