The steiner problem in graphs
From MaRDI portal
Publication:5636923
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
Related Items
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, Enumerate and expand: Improved algorithms for connected vertex cover and tree cover, The kernelization complexity of connected domination in graphs with (no) small cycles, An FPT algorithm in polynomial space for the directed Steiner tree problem with limited number of diffusing nodes, Polynomially solvable special cases of the Steiner problem in planar networks, The role of Steiner hulls in the solution to Steiner tree problems, A dynamic programming approach for the pipe network layout problem, Preprocessing for a map sectorization problem by means of mathematical programming, Improved Approximations for Hard Optimization Problems via Problem Instance Classification, The number of tree stars is \(O^{*}(1.357^k)\), Minimizing Rosenthal potential in multicast games, On the parameterized complexity of finding separators with non-hereditary properties, The Min-Power Multicast Problems in Wireless Ad Hoc Networks: A Parameterized View, Two new criteria for finding Steiner hulls in Steiner tree problems, Path-distance heuristic for the Steiner problem in undirected networks, Definition and algorithms for reliable Steiner tree problem, On the point-to-point connection problem, Speeding up the Dreyfus-Wagner algorithm for minimum Steiner trees, Knowing All Optimal Solutions Does Not Help for TSP Reoptimization, A Layered Graph Model and an Adaptive Layers Framework to Solve Delay-Constrained Minimum Tree Problems, The point-to-point delivery and connection problems: Complexity and algorithms, A dual ascent approach for steiner tree problems on a directed graph, Binary Steiner trees: structural results and an exact solution approach, Steiner trees with \(n\) terminals among \(n+1\) nodes, Heuristics for the Steiner problem in graphs, Steiner trees with bounded RC-delay, Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem, A partition-based relaxation for Steiner trees, Finding induced trees, Algorithmic aspects of Steiner convexity and enumeration of Steiner trees, Two variations of the minimum Steiner problem, Using structured steiner trees for hierarchical global routing, Minimum-weight two-connected spanning networks, Complexity of independency and cliquy trees, Complexity of Steiner Tree in Split Graphs - Dichotomy Results, Non-cooperative tree creation, A multivariate analysis of the strict terminal connection problem, Topological indices based on 2- or 3-eccentricity to predict anti-HIV activity, Vertex and edge covers with clustering properties: Complexity and algorithms, Computing optimal rectilinear Steiner trees: A survey and experimental evaluation, Parameterized Complexity of Team Formation in Social Networks, On approximate preprocessing for domination and hitting subgraphs with connected deletion sets, Minimal connected enclosures on an embedded planar graph, Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals, Approximating Subdense Instances of Covering Problems, Multiple hypernode hitting sets and smallest two-cores with targets, Sorting can exponentially speed up pure dynamic programming, The dynamic predicate stashing copy problem and the Steiner problem in graphs, Neural and delay based heuristics for the Steiner problem in networks, Revising Johnson's table for the 21st century, The number of tree stars is O*(1.357k), Steiner's problem in double trees, Approximability of minimum certificate dispersal with tree structures, Tree polytope on 2-trees, Tight bounds on subexponential time approximation of set cover and related problems
Cites Work
