An algorithm for minimum cost arc-connectivity orientations

DOI10.1007/s00453-008-9179-xzbMath1187.05043OpenAlexW2075939699MaRDI QIDQ848842

Satoru Iwata, Yusuke Kobayashi

Publication date: 23 February 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9179-x

zbMATH Keywords

dijoingraph orientationarc-connectivitycrossing familysubmodular flow

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (4)

Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams ⋮ On 2-strong connectivity orientations of mixed graphs and related problems ⋮ Fractional packing in ideal clutters ⋮ Enumerating \(k\)-arc-connected orientations

Cites Work

• Unnamed Item
• Unnamed Item
• Matrix multiplication via arithmetic progressions
• How to make a digraph strongly connected
• On two minimax theorems in graph
• A matroid approach to finding edge connectivity and packing arborescences
• On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
• A Minimax Theorem for Directed Graphs
• An Algorithm for Submodular Functions on Graphs
• Centroids, Representations, and Submodular Flows

This page was built for publication: An algorithm for minimum cost arc-connectivity orientations