Directed Steiner problems with connectivity constraints

DOI10.1016/0166-218X(93)90086-4zbMath0789.68106WikidataQ127343099 ScholiaQ127343099MaRDI QIDQ1315992

Geir Dahl

Publication date: 17 March 1994

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

zbMATH Keywords

facetscutting plane algorithmconnectivity constraintsdirected Steiner problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items (4)

Capacity-preserving subgraphs of directed flow networks ⋮ Steiner problems on directed acyclic graphs ⋮ Two variations of the minimum Steiner problem ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimum-weight two-connected spanning networks
• On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
• On the 0,1 facets of the set covering polytope
• On the facial structure of the set covering polytope
• Geometric algorithms and combinatorial optimization
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• A dual ascent approach for steiner tree problems on a directed graph
• A quick method for finding shortest pairs of disjoint paths
• Integer Polyhedra Arising from Certain Network Design Problems with Connectivity Constraints
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity Constraints
• Facets for Polyhedra Arising in the Design of Communication Networks with Low-Connectivity Constraints
• Disjoint paths in a network
• Optimum branchings

This page was built for publication: Directed Steiner problems with connectivity constraints