An algorithm for minimum cost arc-connectivity orientations

DOI10.1007/S00453-008-9179-XMaRDI QIDQ848842zbMATH OpenOpenAlexFDO

Authors 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

graph orientationarc-connectivitydijoincrossing familysubmodular flow

Mathematics Subject Classification ID

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

Recommendations

• On orientations maximizing total arc-connectivity
• Approximating Minimum Cost Connectivity Orientation and Augmentation
• Approximating minimum cost connectivity orientation and augmentation
• Faster algorithms for minimum-link paths with restricted orientations
• Approximation algorithms for the arc orienteering problem
• scientific article; zbMATH DE number 56364
• Minimum cost disjoint paths under arc dependences. Algorithms for practice.
• Publication:4886063
• An approximation algorithm for minimum-cost vertex-connectivity problems

Cites work

• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• scientific article; zbMATH DE number 2246594 (Why is no real title available?)
• A Minimax Theorem for Directed Graphs
• A matroid approach to finding edge connectivity and packing arborescences
• An Algorithm for Submodular Functions on Graphs
• Centroids, Representations, and Submodular Flows
• How to make a digraph strongly connected
• Matrix multiplication via arithmetic progressions
• On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
• On two minimax theorems in graph

Cited in

(10)

• scientific article; zbMATH DE number 3891093 (Why is no real title available?)
• On 2-strong connectivity orientations of mixed graphs and related problems
• Enumerating \(k\)-arc-connected orientations
• Fractional packing in ideal clutters
• Fast cycle canceling algorithms for minimum cost submodular flow
• Approximating minimum cost connectivity orientation and augmentation
• Using Four Cost Measures to Determine Arc Reversal Orderings
• Approximating Minimum Cost Connectivity Orientation and Augmentation
• Fast edge orientation for unweighted graphs
• Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams

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

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