Faster Network Algorithms Based on Graph Decomposition

No abstract is available for this paper.

• Publication year

  2018

• Venue

  Workshop on Algorithms and Computation

• Publication date

  2018-03-03

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-319-75172-6_8
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Max flows in O(nm) time, or better

  2013cited by this paper
• Improved algorithms for min cut and max flow in undirected planar graphs

  2011cited by this paper
• An O(n log n) algorithm for maximum st-flow in a directed planar graph

  2009cited by this paper
• Invitation to Fixed-Parameter Algorithms

  2006cited by this paper
• A Linear Time Implementation of SPQR-Trees

  2000cited by this paper
• Computing Mimicking Networks

  1998cited by this paper
• On-line maintenance of triconnected components with SPQR-trees

  1996cited by this paper
• Counterexamples for Directed and Node Capacitated Cut-Trees

  1995cited by this paper
• All-Pairs Min-Cut in Sparse Networks

  1995cited by this paper
• Characterizations of k-terminal flow networks and computing network flows in partial k-trees

  1995cited by this paper
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph

  1994cited by this paper
• A faster deterministic maximum flow algorithm

  1992cited by this paper
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs

  1992cited by this paper
• Using cellular graph embeddings in solving all pairs shortest paths problems

  1989cited by this paper
• A new approach to the maximum-flow problem

  1988cited by this paper
• A decomposition algorithm for multi-terminal networks flows

  1986cited by this paper
• Fast Algorithms for Finding Nearest Common Ancestors

  1984cited by this paper
• Computing on a free tree via complexity-preserving mappings

  1984cited by this paper
• Graph minors. III. Planar tree-width

  1984cited by this paper
• Algorithm 447: efficient algorithms for graph manipulation

  1973cited by this paper
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

  1972cited by this paper
• Multi-Terminal Network Flows

  1961cited by this paper
• Maximal Flow Through a Network

  1956cited by this paper

• No citing papers are available for this paper.