A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs

DOI10.1007/978-3-642-00202-1_17MaRDI QIDQ3605497zbMATH OpenOpenAlexFDO

Authors Louis Ibarra

Publication date 24 February 2009

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-00202-1_17

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)

Recommendations

• A fully dynamic graph algorithm for recognizing interval graphs
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• Fully dynamic recognition of proper circular-arc graphs
• Fully dynamic representations of interval graphs
• A fully dynamic algorithm for recognizing and representing chordal graphs

Cites work

• scientific article; zbMATH DE number 1303554 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithmic graph theory and perfect graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
• Fully dynamic algorithms for chordal graphs and split graphs
• Introduction to algorithms
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Simple linear time recognition of unit interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The NP-completeness column: an ongoing guide
• The clique-separator graph for chordal graphs
• Topics in Intersection Graph Theory

Cited in

(16)

• scientific article; zbMATH DE number 6810347 (Why is no real title available?)
• Fully dynamic recognition of proper circular-arc graphs
• Distance queries over dynamic interval graphs
• A linear time recognition algorithm for proper interval graphs
• A simple algorithm to find Hamiltonian cycles in proper interval graphs
• Fully dynamic representations of interval graphs
• scientific article; zbMATH DE number 1303554 (Why is no real title available?)
• A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
• The clique-separator graph for chordal graphs
• A survey of the algorithmic aspects of modular decomposition
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• A fully dynamic graph algorithm for recognizing interval graphs
• A dynamic distributed approach to representing proper interval graphs
• Recognizing d-interval graphs and d-track interval graphs
• Fully dynamic representations of interval graphs

This page was built for publication: A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs

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