Faster network algorithms based on graph decomposition

DOI10.1007/978-3-319-75172-6_8MaRDI QIDQ1641101zbMATH OpenOpenAlexFDO

Authors Manas Jyoti Kashyop, Tsunehiko Nagayama, Kunihiko Sadakane

Publication date 15 June 2018

Full work available at URL https://doi.org/10.1007/978-3-319-75172-6_8

zbMATH Keywords

data structuresMaximum Flow problem

Mathematics Subject Classification ID

Flows in graphs (05C21) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Recommendations

• Faster algorithms for shortest path and network flow based on graph decomposition
• A decomposition algorithm for multi-terminal network flows
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Beyond the flow decomposition barrier
• scientific article; zbMATH DE number 177817

Cited in

(10)

• A decomposition algorithm for multi-terminal network flows
• A fast network-decomposition algorithm and its applications to constant-time distributed computation
• Flow decompositions in external memory
• Speeding up Graph Algorithms via Switching Classes
• scientific article; zbMATH DE number 1182573 (Why is no real title available?)
• DECOMPOSITION ALGORITHMS TO COMPUTE THE QUICKEST TIME DISTRIBUTION IN DYNAMIC NETWORKS
• Faster algorithms for shortest path and network flow based on graph decomposition
• A fast algorithm of constructing decomposition of multipole flows
• Simple linear flow decomposition algorithms on trees, circles, and augmented trees
• Fast network decomposition

This page was built for publication: Faster network algorithms based on graph decomposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1641101)