The steiner problem in graphs

DOI10.1002/net.3230010302zbMath0229.05125OpenAlexW1996668544MaRDI QIDQ5636923

Stuart E. Dreyfus, Robert A. Wagner

Publication date: 1972

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230010302

Mathematics Subject Classification ID

Graph theory (05C99)

Related Items (only showing first 100 items - show all)

A branch-and-price algorithm for switch-box routing ⋮ ECCENTRIC STEINER DISTANCE SUM OF VICSEK NETWORKS ⋮ RNC-approximation algorithms for the steiner problem ⋮ Covering Vectors by Spaces: Regular Matroids ⋮ MEAN STEINER DISTANCE OF VICSEK NETWORKS ⋮ Stabilizing branch‐and‐price for constrained tree problems ⋮ On the Exact Solution of Prize-Collecting Steiner Tree Problems ⋮ A probably fast, provably optimal algorithm for rectilinear Steiner trees ⋮ Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ⋮ On the computational difficulty of the terminal connection problem ⋮ On the lossy kernelization for connected treedepth deletion set ⋮ On the complexity of the cable-trench problem ⋮ On the complexity of the bilevel minimum spanning tree problem ⋮ A linear programming based approach to the Steiner tree problem with a fixed number of terminals ⋮ Steiner connectivity problems in hypergraphs ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems ⋮ P versus NPC: minimum Steiner trees in convex split graphs ⋮ New pricing strategies and an effective exact solution framework for profit-oriented ring arborescence problems ⋮ Navigational guidance -- a deep learning approach ⋮ On convexity in split graphs: complexity of Steiner tree and domination ⋮ An ETH-tight algorithm for bidirected Steiner connectivity ⋮ A vertex-separator-based integer linear programming formulation for the partitioned Steiner tree problem ⋮ Unnamed Item ⋮ Reoptimization of Steiner Trees ⋮ Steiner problems on directed acyclic graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On finding steiner vertices ⋮ Fuzzy Replacement Analysis ⋮ Faster Steiner Tree Computation in Polynomial-Space ⋮ Strong Steiner Tree Approximations in Practice ⋮ A Lagrangean-based decomposition approach for the link constrained Steiner tree problem ⋮ A Near-Linear Approximation Scheme for Multicuts of Embedded Graphs With a Fixed Number of Terminals ⋮ An Exact Algorithm for the Steiner Forest Problem ⋮ Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View ⋮ Cost-minimal trees in directed acyclic graphs ⋮ A branch-and-price algorithm for the Steiner tree packing problem. ⋮ Unnamed Item ⋮ On the Hardness of Reoptimization ⋮ Heuristic algorithms for packing of multiple-group multicasting ⋮ Parameterized Complexity of Directed Steiner Tree on Sparse Graphs ⋮ Implications, conflicts, and reductions for Steiner trees ⋮ Approximation Limitations of Pure Dynamic Programming ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ Complexity of the Steiner Network Problem with Respect to the Number of Terminals ⋮ Exploring the Tractability of the Capped Hose Model ⋮ Lossy Kernels for Hitting Subgraphs ⋮ Multiple Hypernode Hitting Sets and Smallest Two-Cores with Targets ⋮ Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices ⋮ The computation of nearly minimal Steiner trees in graphs ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems ⋮ On Hop-Constrained Steiner Trees in Tree-Like Metrics ⋮ Strongly polynomial algorithm for two special minimum concave cost network flow problems ⋮ A primal-dual approximation algorithm for the Steiner forest problem ⋮ Augmenting weighted graphs to establish directed point-to-point connectivity ⋮ The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets ⋮ The Turing way to parameterized complexity ⋮ On the terminal connection problem ⋮ Greedy can beat pure dynamic programming ⋮ Minimum Certificate Dispersal with Tree Structures ⋮ Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree ⋮ Reoptimization of Steiner trees: changing the terminal set ⋮ Steiner problem in Halin networks ⋮ Steiner Trees with Bounded RC-Delay ⋮ Unnamed Item ⋮ On Directed Steiner Trees with Multiple Roots ⋮ Parameterized complexity of reconfiguration of atoms ⋮ The Influence of Preprocessing on Steiner Tree Approximations ⋮ Computing optimal Steiner trees in polynomial space ⋮ Directed Steiner trees with diffusion costs ⋮ The propagation of updates to relational tables in a distributed database system ⋮ Steiner tree in \(k\)-star caterpillar convex bipartite graphs: a dichotomy ⋮ The point-to-point connection problem - analysis and algorithms ⋮ Packing Steiner trees: A cutting plane algorithm and computational results ⋮ Extending the kernel for planar Steiner tree to the number of Steiner vertices ⋮ Parameterized complexity of secluded connectivity problems ⋮ A factoring approach for the Steiner tree problem in undirected networks ⋮ The density maximization problem in graphs ⋮ The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy ⋮ Parameterized complexity of Min-power multicast problems in wireless ad hoc networks ⋮ Robust reoptimization of Steiner trees ⋮ The homogeneous broadcast problem in narrow and wide strips. I: Algorithms ⋮ On the approximability of dense Steiner problems ⋮ Improved Steiner tree algorithms for bounded treewidth ⋮ Parameterized approximation via fidelity preserving transformations ⋮ Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems ⋮ Proving phylogenetic trees minimal with l-clustering and set partitioning ⋮ Faster algorithm for optimum Steiner trees ⋮ Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm ⋮ FPT and kernelization algorithms for the induced tree problem ⋮ Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems ⋮ Parameterized complexity of team formation in social networks ⋮ Smoothed analysis of partitioning algorithms for Euclidean functionals ⋮ Parameterized study of Steiner tree on unit disk graphs ⋮ Combination algorithms for Steiner tree variants ⋮ A survey of dynamic network flows ⋮ Connected facility location via random facility sampling and core detouring ⋮ On the edge capacitated Steiner tree problem ⋮ Network design with a discrete set of traffic matrices

Cites Work

• Steiner Minimal Trees

This page was built for publication: The steiner problem in graphs