Mimicking Networks and Succinct Representations of Terminal Cuts

@), which is moreover a minor of G. On the other hand, some planar networks G require |E(G')| ≥ Ω(k2). For general networks, we show that certain bipartite graphs only admit mimicking networks of size |V(G')| ≥ 2Ω(k), and moreover, every data structure that stores the minimum cut value between all bipartitions of the terminals must use 2Ω(k) machine words.

• Publication year

  2012

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2012-07-26

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/1.9781611973105.128arXiv 1207.6246
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On mimicking networks representing minimum terminal cuts

  2012cited by this paper
• Preserving Terminal Distances Using Minors

  2012cited by this paper
• On vertex sparsifiers with Steiner nodes

  2012cited by this paper
• Vertex Sparsifiers: New Results from Old Techniques

  2010cited by this paper
• Vertex Sparsifiers and Abstract Rounding Algorithms

  2010cited by this paper
• Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size

  2009cited by this paper
• Twice-ramanujan sparsifiers

  2008cited by this paper
• Approximating s – t Minimum Cuts in ~ O(n 2 ) Time

  2007cited by this paper
• Sparse Sourcewise and Pairwise Distance Preservers

  2006cited by this paper
• Computing Mimicking Networks

  1998influential reference
• Characterizing Multiterminal Flow Networks and Computing Flows in Networks of Small Treewidth

  1998influential reference
• Probabilistic approximation of metric spaces and its algorithmic applications

  1996cited by this paper
• Discrete Applied Mathematics

  1993cited by this paper
• Graph Spanners: a Survey

  1992cited by this paper
• Clique partitions, graph compression and speeding-up algorithms

  1991cited by this paper
• A Graph-Theoretic Game and its Application to the k-Server Problem (Extended Abstract)

  1991cited by this paper
• Succinct representation of general unlabeled graphs

  1990cited by this paper
• Graph spanners

  1989cited by this paper
• Finding near optimal separators in planar graphs

  1987cited by this paper
• An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem

  1985cited by this paper
• On the succinct representation of graphs

  1984cited by this paper
• Lower bound of the hadwiger number of graphs by their average degree

  1984cited by this paper
• Multi-Terminal Network Flows

  1961cited by this paper
• Maximal Flow Through a Network

  1956cited by this paper

• Lower Bounds on Flow Sparsifiers with Steiner Nodes

  2026cites this paper
• Notes on the Linear Algebraic View of Regularity Lemmas

  2025cites this paper
• The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs

  2024cites this paper
• Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time

  2024cites this paper
• Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs

  2024cites this paper
• Nearly-Tight Bounds for Flow Sparsifiers in Quasi-Bipartite Graphs

  2024cites this paper
• On (1+ε)-Approximate Flow Sparsifiers

  2023cites this paper
• Representative set statements for delta-matroids and the Mader delta-matroid

  2023cites this paper
• Cactus Representations in Polylogarithmic Max-flow via Maximal Isolating Mincuts

  2023cites this paper
• Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families

  2023cites this paper
• Cut Sparsification and Succinct Representation of Submodular Hypergraphs

  2023cites this paper
• Near-Linear $\varepsilon$-Emulators for Planar Graphs

  2022cites this paper
• Quasipolynomial Multicut-mimicking Networks and Kernels for Multiway Cut Problems

  2022cites this paper
• Exact Flow Sparsification Requires Unbounded Size

  2022cites this paper
• Vertex Sparsifiers for Hyperedge Connectivity

  2022cites this paper
• Optimal Vertex-Cut Sparsification of Quasi-Bipartite Graphs

  2022cites this paper
• Almost-linear ε-emulators for planar graphs

  2022cites this paper
• A Constant-factor Approximation for Weighted Bond Cover

  2021cites this paper
• Minor Sparsifiers and the Distributed Laplacian Paradigm

  2020cites this paper
• Vertex Sparsification for Edge Connectivity in Polynomial Time

  2020cites this paper
• Near-Linear-Time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs

  2020cites this paper
• Tight Bound on Vertex Cut Sparsifiers in Directed Acyclic Graphs

  2020cites this paper
• IMPROVED GUARANTEES FOR VERTEX SPARSIFICATION IN 1 PLANAR GRAPHS

  2020influential citation
• Vertex Sparsification for Edge Connectivity

  2020cites this paper
• Scattering and Sparse Partitions, and Their Applications

  2020cites this paper
• On quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems

  2020cites this paper
• Fully dynamic spectral vertex sparsifiers and applications

  2019cites this paper
• NC Algorithms for Computing a Perfect Matching, the Number of Perfect Matchings, and a Maximum Flow in One-Crossing-Minor-Free Graphs

  2019cites this paper
• Dynamic Graph Algorithms and Graph Sparsification: New Techniques and Connections

  2019influential citation
• Mimicking Networks Parameterized by Connectivity

  2019cites this paper
• STEINER POINT REMOVAL WITH DISTORTION \bfitO (log \bfitk ) USING THE RELAXED-VORONOI ALGORITHM\ast

  2019cites this paper
• NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs

  2018cites this paper
• 04 03 8 v 1 [ cs . D S ] 1 1 A pr 2 01 8 Fully Dynamic Effective Resistances

  2018cites this paper
• Fully Dynamic Effective Resistances

  2018cites this paper
• NC Algorithms for Perfect Matching and Maximum Flow in One-Crossing-Minor-Free Graphs

  2018cites this paper
• Steiner Point Removal with Distortion O(log k)

  2017cites this paper
• Transport in Unsteady Flows: from Deterministic Structures to Stochastic Models and Back Again (17w5048)

  2017cites this paper
• Steiner Point Removal - Distant Terminals Don't (Really) Bother

  2017cites this paper
• An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs

  2017cites this paper
• Improved Guarantees for Vertex Sparsification in Planar Graphs

  2017influential citation
• Refined Vertex Sparsifiers of Planar Graphs

  2017influential citation
• Vertex Sparsification in Trees

  2016cites this paper
• Tight Bounds for Gomory-Hu-like Cut Counting

  2015cites this paper
• Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches

  2015cites this paper
• Algorithms for Graph Connectivity and Cut Problems - Connectivity Augmentation, All-Pairs Minimum Cut, and Cut-Based Clustering

  2014cites this paper
• Degree-3 Treewidth Sparsifiers

  2014cites this paper
• Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs

  2013cites this paper
• Towards (1 + ∊)-Approximate Flow Sparsifiers

  2013cites this paper
• Towards (1+\epsilon)-Approximate Flow Sparsifiers

  2013influential citation
• On mimicking networks representing minimum terminal cuts

  2012cites this paper
• Approximation algorithms and the hardness of approximation

  2011cites this paper
• Thesis for the degree

  year unknowncites this paper
• Potential-Based Flows—An Overview

  year unknowncites this paper