Separator-Based Sparsification II: Edge and Vertex Connectivity

DOI10.1137/S0097539794269072MaRDI QIDQ4210152zbMATHOpenAlexDBLPWikidataFDO

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

Publication date 21 September 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539794269072

zbMATH Keywords

analysis of algorithmsplanar graphsvertex connectivitydynamic data structuresedge connectivity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Parallel algorithms in computer science (68W10)

Recommendations

• Separator based sparsification. I: Planarity testing and minimum spanning trees
• Vertex sparsifiers: new results from old techniques
• Vertex Sparsifiers: New Results from Old Techniques
• Efficient edge splitting-off algorithms maintaining all-pairs edge-connectivities
• Efficient edge splitting-off algorithms maintaining all-pairs edge-connectivities
• On vertex sparsifiers with Steiner nodes
• Extensions and limits to vertex sparsification
• A near optimal algorithm for edge separators (preliminary version)
• The emergence of sparse spanners and greedy well-separated pair decomposition
• scientific article; zbMATH DE number 4064516

Cited in

(10)

• Synchronized Planarity with Applications to Constrained Planarity Problems
• Decremental SPQR-trees for Planar Graphs
• Separator based sparsification. I: Planarity testing and minimum spanning trees
• Optimal decremental connectivity in planar graphs
• Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
• Good \(r\)-divisions imply optimal amortized decremental biconnectivity
• Sublinear separators, fragility and subexponential expansion
• A fully dynamic graph algorithm for recognizing interval graphs
• Maintaining dynamic minimum spanning trees: an experimental study
• Fully dynamic representations of interval graphs

This page was built for publication: Separator-Based Sparsification II: Edge and Vertex Connectivity

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