Separator-Based Sparsification II: Edge and Vertex Connectivity

DOI10.1137/S0097539794269072MaRDI QIDQ4210152zbMATH OpenOpenAlexDBLPWikidataFDO

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 algorithmsdynamic data structuresedge connectivityplanar graphsvertex connectivity

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) 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

(12)

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

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)