Tight Bounds for Gomory-Hu-like Cut Counting
From MaRDI portal
Publication:3181053
DOI10.1007/978-3-662-53536-3_12zbMath1417.05090arXiv1511.08647OpenAlexW2963094095MaRDI QIDQ3181053
Robert Krauthgamer, Lior Kamma, Rajesh Chitnis
Publication date: 22 December 2016
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1511.08647
Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Signed and weighted graphs (05C22)
Related Items (3)
Tight Bounds for Gomory-Hu-like Cut Counting ⋮ Mincut sensitivity data structures for the insertion of an edge ⋮ Mincut Sensitivity Data Structures for the Insertion of an Edge
Cites Work
- Unnamed Item
- Ancestor tree for arbitrary multi-terminal cut functions
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- Computing mimicking networks
- On mimicking networks representing minimum terminal cuts
- Tight Bounds for Gomory-Hu-like Cut Counting
- Maximal Flow Through a Network
- Very Simple Methods for All Pairs Network Flow Analysis
- An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs
- Multi-Terminal Network Flows
- Labeling Schemes for Flow and Connectivity
- Counterexamples for Directed and Node Capacitated Cut-Trees
This page was built for publication: Tight Bounds for Gomory-Hu-like Cut Counting
