Directed Network Design with Orientation Constraints

DOI10.1137/S0895480100380112MaRDI QIDQ5317612zbMATH OpenOpenAlexFDO

Authors Sanjeev Khanna, Joseph (Seffi) Naor, F. Bruce Shepherd

Publication date 16 September 2005

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480100380112

zbMATH Keywords

approximation algorithmsconnectivityorientationsubmodular flow

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• scientific article; zbMATH DE number 1445363
• scientific article; zbMATH DE number 1342141
• Algorithms for a network design problem with crossing supermodular demands
• Approximating minimum cost connectivity orientation and augmentation

Cited in

(12)

• On reachability mixed arborescence packing
• The complexity of the proper orientation number
• Directing Road Networks by Listing Strong Orientations
• A Survey on Covering Supermodular Functions
• scientific article; zbMATH DE number 1342141 (Why is no real title available?)
• scientific article; zbMATH DE number 597594 (Why is no real title available?)
• Approximating Minimum Cost Connectivity Orientation and Augmentation
• Improved Orientations of Physical Networks
• scientific article; zbMATH DE number 1445363 (Why is no real title available?)
• Approximating minimum cost connectivity orientation and augmentation
• Minimum cost nowhere-zero flows and cut-balanced orientations
• On the \(L_{\infty}\)-norm of extreme points for crossing supermodular directed network LPs

This page was built for publication: Directed Network Design with Orientation Constraints

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