Separator-Based Sparsification II: Edge and Vertex Connectivity
DOI10.1137/S0097539794269072zbMATH Open0914.68042DBLPjournals/siamcomp/EppsteinGIS98OpenAlexW1997906261WikidataQ101437882 ScholiaQ101437882MaRDI QIDQ4210152FDOQ4210152
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
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
Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Parallel algorithms in computer science (68W10)
Cited In (8)
- Maintaining dynamic minimum spanning trees: an experimental study
- Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
- Decremental SPQR-trees for Planar Graphs
- Good \(r\)-divisions imply optimal amortized decremental biconnectivity
- Synchronized Planarity with Applications to Constrained Planarity Problems
- Sublinear separators, fragility and subexponential expansion
- A fully dynamic graph algorithm for recognizing interval graphs
- 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)
