A fully dynamic graph algorithm for recognizing interval graphs

DOI10.1007/S00453-009-9291-6MaRDI QIDQ1957648zbMATH OpenOpenAlexFDO

Authors Louis Ibarra

Publication date 27 September 2010

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-009-9291-6

zbMATH Keywords

Chordal graphClique treeDynamic graph algorithmInterval graphPQ-tree

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
• Fully dynamic representations of interval graphs
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• A fully dynamic algorithm for recognizing and representing chordal graphs
• Fully dynamic representations of interval graphs

Cites work

• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• A Fully Dynamic Graph Algorithm for Recognizing 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
• Counting clique trees and computing perfect elimination schemes in parallel
• Efficiency of a Good But Not Linear Set Union Algorithm
• Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
• Fully dynamic algorithms for chordal graphs and split graphs
• Graph Classes: A Survey
• scientific article; zbMATH DE number 1303554 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• Incidence matrices and interval graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Separator-Based Sparsification II: Edge and Vertex Connectivity
• Simple linear time recognition of unit interval graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Sparsification—a technique for speeding up dynamic graph algorithms
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The clique-separator graph for chordal graphs
• The NP-completeness column: an ongoing guide
• Topics in Intersection Graph Theory

Cited in

(13)

• Fully dynamic representations of interval graphs
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
• Fully dynamic recognition of proper circular-arc graphs
• Recognizing d-interval graphs and d-track interval graphs
• Computing the clique-separator graph for an interval graph in linear time
• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
• scientific article; zbMATH DE number 4049085 (Why is no real title available?)
• scientific article; zbMATH DE number 1303554 (Why is no real title available?)
• Backup 2-center on interval graphs
• Fully dynamic representations of interval graphs
• Distance queries over dynamic interval graphs

This page was built for publication: A fully dynamic graph algorithm for recognizing interval graphs

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