scientific article; zbMATH DE number 7205022
From MaRDI portal
Publication:5111733
DOI10.4230/LIPIcs.ESA.2017.44zbMath1442.68171MaRDI QIDQ5111733
Pan Peng, Gramoz Goranci, Monika R. Henzinger
Publication date: 27 May 2020
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Signed and weighted graphs (05C22) Metric embeddings as related to computational problems and algorithms (68R12)
Related Items
Unnamed Item ⋮ Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm ⋮ Refined Vertex Sparsifiers of Planar Graphs ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ Unnamed Item ⋮ An exponential lower bound for cut sparsifiers in planar graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A node-capacitated Okamura-Seymour theorem
- Circular planar graphs and resistor networks
- Multicommodity flows in planar graphs
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- On the distortion required for embedding finite metric spaces into normed spaces
- On mimicking networks representing minimum terminal cuts
- Metric extension operators, vertex sparsifiers and Lipschitz extendability
- Preserving Terminal Distances Using Minors
- Extensions and limits to vertex sparsification
- Vertex Sparsification in Trees
- Spectral Sparsification of Graphs
- Sparse Sourcewise and Pairwise Distance Preservers
- Dynamic Plane Transitive Closure
- Approximate distance oracles
- A Tight Lower Bound for the Steiner Point Removal Problem on Trees
- Universality considerations in VLSI circuits
- Delta-Wye Transformations and the Efficient Reduction of Two-Terminal Planar Graphs
- Linear Size Distance Preservers
- Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
- Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
- Edge-Disjoint Paths in Planar Graphs with Constant Congestion
- Refined Vertex Sparsifiers of Planar Graphs
- Towards (1 + ∊)-Approximate Flow Sparsifiers
- On vertex sparsifiers with Steiner nodes
- Routing in undirected graphs with constant congestion
- Compact oracles for reachability and approximate distances in planar digraphs
- Embedding k-Outerplanar Graphs into l1
- Cutting Corners Cheaply, or How to Remove Steiner Points
- The Transitive Reduction of a Directed Graph
- Mimicking Networks and Succinct Representations of Terminal Cuts
- Vertex Sparsifiers: New Results from Old Techniques
