Some insights on dynamic maintenance of Gomory-Hu tree in cactus graphs and general graphs

DOI10.1007/978-3-031-25211-2_18OpenAlexW4318022992MaRDI QIDQ6132538

Sushanta Karmakar, Vineet Malik

Publication date: 17 August 2023

Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-25211-2_18

zbMATH Keywords

cactus graphmin-cutdynamic graphGomory-Hu tree

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Fully-dynamic min-cut
• Maintaining the classes of 4-edge-connectivity in a graph on-line
• Mincut sensitivity data structures for the insertion of an edge
• Revisiting parametric multi-terminal problems: maximum flows, minimum cuts and cut-tree computations
• Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time
• Maximal Flow Through a Network
• Very Simple Methods for All Pairs Network Flow Analysis
• A new approach to the maximum-flow problem
• Multi-Terminal Network Flows
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time
• Fast and Simple Fully-Dynamic Cut Tree Construction
• Min st -Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
• When Do Gomory--Hu Subtrees Exist?
• Faster energy maximization for faster maximum flow
• New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs

This page was built for publication: Some insights on dynamic maintenance of Gomory-Hu tree in cactus graphs and general graphs