Separator based sparsification for dynamic planar graph algorithms

DOI10.1145/167088.167159MaRDI QIDQ5248488zbMATH OpenOpenAlexFDO

Authors David Eppstein, Giuseppe F. Italiano, Thomas H. Spencer, Zvi Galil

Publication date 7 May 2015

Published in Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/167088.167159

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cited in

(17)

• Dynamic and static algorithms for optimal placement of resources in a tree
• Fully dynamic biconnectivity in graphs
• Analysis and experimental study of heuristics for job scheduling reoptimization problems
• On-line convex planarity testing
• Discovering recurring activity in temporal networks
• Data structures for two-edge connectivity in planar graphs
• Dynamic Distance Hereditary Graphs Using Split Decomposition
• Output-sensitive reporting of disjoint paths (extended abstract)
• Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning
• Fully Dynamic Transitive Closure in plane dags with one source and one sink
• Maintaining minimum spanning trees in dynamic graphs
• Finding the k Shortest Paths
• Certificates and fast algorithms for biconnectivity in fully-dynamic graphs
• A dynamic topological sort algorithm for directed acyclic graphs
• A dynamic algorithm for line graph recognition
• Dynamic connectivity in digital images
• Using sparsification for parametric minimum spanning tree problems

This page was built for publication: Separator based sparsification for dynamic planar graph algorithms

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