Reconstructing edge-disjoint paths faster

DOI10.1016/J.ORL.2015.12.017zbMath1408.68120OpenAlexW2222334279MaRDI QIDQ1785736

Chao Xu

Publication date: 1 October 2018

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2015.12.017

zbMATH Keywords

connectivityedge-disjoint pathsancestor tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Cites Work

• Unnamed Item
• Computing on a free tree via complexity-preserving mappings
• Ancestor tree for arbitrary multi-terminal cut functions
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Reconstructing edge-disjoint paths.
• A data structure for dynamic trees
• Breaking the O(n^2.5) Deterministic Time Barrier for Undirected Unit-Capacity Maximum Flow

This page was built for publication: Reconstructing edge-disjoint paths faster