Directed Steiner problems with connectivity constraints

DOI10.1016/0166-218X(93)90086-4zbMATH Open0789.68106WikidataQ127343099 ScholiaQ127343099MaRDI QIDQ1315992FDOQ1315992

Authors: Geir Dahl 

Publication date: 17 March 1994

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

Recommendations

• An approach for the Steiner problem in directed graphs
• Approximation Algorithms for Directed Steiner Problems
• scientific article; zbMATH DE number 1303557
• Set connectivity problems in undirected graphs and the directed Steiner network problem
• Set connectivity problems in undirected graphs and the directed Steiner network problem
• The complexity landscape of fixed-parameter directed Steiner network problems
• The Steiner connectivity problem
• A constrained Steiner tree problem
• Steiner tree problems
• Steiner tree problems

zbMATH Keywords

facetscutting plane algorithmconnectivity constraintsdirected Steiner problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Geometric algorithms and combinatorial optimization
• Optimum branchings
• Facets for Polyhedra Arising in the Design of Communication Networks with Low-Connectivity Constraints
• Disjoint paths in a network
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• 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
• Integer Polyhedra Arising from Certain Network Design Problems with Connectivity Constraints
• Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low-Connectivity Constraints
• Minimum-weight two-connected spanning networks
• A quick method for finding shortest pairs of disjoint paths
• Title not available (Why is that?)
• A dual ascent approach for steiner tree problems on a directed graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (18)

• Optimal connection problem of single source multiple sinks on directed networks
• The Minimum Weight In-Tree Cover Problem
• Multicommodity disconnecting set problem
• Two variations of the minimum Steiner problem
• STEINER-diagrams
• Lehman's theorem and the directed Steiner tree problem
• On directed Steiner trees with multiple roots
• Steiner diagrams and \(k\)-star hubs
• Title not available (Why is that?)
• Capacity-preserving subgraphs of directed flow networks
• Steiner problems on directed acyclic graphs
• Classes of directed graded graphs with polynomially solvable cardinality Steiner problem
• Rooted \(k\)-connections in digraphs
• Title not available (Why is that?)
• The line connectivity problem
• The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals
• An approach for the Steiner problem in directed graphs
• The Steiner connectivity problem

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

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