Steiner trees, partial 2–trees, and minimum IFI networks
From MaRDI portal
Publication:3311677
DOI10.1002/NET.3230130202zbMath0529.68036OpenAlexW2048013200MaRDI QIDQ3311677
Charles J. Colbourn, Joseph A. Wald
Publication date: 1983
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.3230130202
NP-completenesslinear time algorithmlinear time Steiner tree algorithmminimum isolated failure immune networks
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)
Related Items (84)
Perfect edge domination and efficient edge domination in graphs ⋮ Arborescence polytopes for series-parallel graphs ⋮ The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets ⋮ The Steiner tree problem. II: Properties and classes of facets ⋮ Computing directed Steiner path covers ⋮ Heuristics for the network design problem with connectivity requirements ⋮ Characterization of partial 3-trees in terms of three structures ⋮ A stronger lower bound on parametric minimum spanning trees ⋮ A column generation approach for solving a non-temporal forest harvest model with spatial structure constraints ⋮ Steiner problem in Halin networks ⋮ Canonical representations of partial 2-and 3-trees ⋮ Minimum-maximal matching in series-parallel graphs ⋮ Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs ⋮ Characterization and Recognition of Partial 3-Trees ⋮ A parallelizable lexicographically first maximal edge-induced subgraph problem ⋮ Cuts, matrix completions and graph rigidity ⋮ Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs ⋮ Constructive linear time algorithms for branchwidth ⋮ The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues ⋮ Complexity of Finding Embeddings in a k-Tree ⋮ Structural conditions for cycle completable graphs ⋮ Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs ⋮ A factoring approach for the Steiner tree problem in undirected networks ⋮ Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results ⋮ Intersecting longest paths ⋮ Characterizing graphs of maximum matching width at most 2 ⋮ Homomorphism bounds of signed bipartite \(K_4\)-minor-free graphs and edge-colorings of \(2k\)-regular \(K_4\)-minor-free multigraphs ⋮ A simple linear time algorithm for triangulating three-colored graphs ⋮ Improved Steiner tree algorithms for bounded treewidth ⋮ Toughness and spanning trees in K4‐minor‐free graphs ⋮ Risk models for the prize collecting Steiner tree problems with interval data ⋮ P versus NPC: minimum Steiner trees in convex split graphs ⋮ On convexity in split graphs: complexity of Steiner tree and domination ⋮ A PTAS for weight constrained Steiner trees in series--parallel graphs. ⋮ The complexity of the locally connected spanning tree problem ⋮ On the area of constrained polygonal linkages ⋮ Forbidden minors characterization of partial 3-trees ⋮ On two dual classes of planar graphs ⋮ On the extension of a partial metric to a tree metric ⋮ Minimum size tree-decompositions ⋮ Network Resilience ⋮ Permutation graphs: Connected domination and Steiner trees ⋮ Concepts of signed graph coloring ⋮ Stronger MIP formulations for the Steiner forest problem ⋮ Algorithms for recognition of regular properties and decomposition of recursive graph families ⋮ The role of Steiner hulls in the solution to Steiner tree problems ⋮ Temporal constraint networks ⋮ A stronger lower bound on parametric minimum spanning trees ⋮ A note on integral generalized flows in directed partial 2-trees ⋮ Problems with generalized Steiner problems ⋮ Characterization and complexity of uniformly nonprimitive labeled 2-structures ⋮ Minimum size tree-decompositions ⋮ A technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-paths ⋮ Canonical representations of partial 2- and 3-trees ⋮ The most vital edges with respect to the number of spanning trees in two- terminal series-parallel graphs ⋮ Efficient sets in partial \(k\)-trees ⋮ On the SPANNING \(k\)-TREE problem ⋮ Computing residual connectedness reliability for restricted networks ⋮ Minimum perfect bipartite matchings and spanning trees under categorization ⋮ Tree decomposition and discrete optimization problems: a survey ⋮ An O\((nm)\) algorithm for a special case of the multimedian location problem on a tree ⋮ Steiner trees and polyhedra ⋮ Using a hybrid of exact and genetic algorithms to design survivable networks ⋮ Complexity of Steiner Tree in Split Graphs - Dichotomy Results ⋮ Cycle stochastic graphs: Structural and forbidden graph characterizations ⋮ Assortment optimization under the multinomial logit model with product synergies ⋮ Bounds on vertex colorings with restrictions on the union of color classes ⋮ Weighted connected domination and Steiner trees in distance-hereditary graphs ⋮ Finding a Small Number of Colourful Components ⋮ A linear time algorithm for computing the most reliable source on a series--parallel graph with unreliable edges ⋮ MULTI-TERMINAL NETWORK CONNECTEDNESS ON SERIES-PARALLEL NETWORKS ⋮ The graphs for which the maximum multiplicity of an eigenvalue is two ⋮ Revising Johnson's table for the 21st century ⋮ Algorithms for the clique problem with multiple-choice constraints under a series-parallel dependency graph ⋮ The traveling salesman problem on a graph and some related integer polyhedra ⋮ Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree ⋮ Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions ⋮ Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey ⋮ Steiner's problem in double trees ⋮ On some optimization problems on \(k\)-trees and partial \(k\)-trees ⋮ Finding maximum cliques in arbitrary and in special graphs ⋮ The Steiner tree polytope and related polyhedra ⋮ Tree polytope on 2-trees ⋮ Generalized Steiner problem in outerplanar networks
Cites Work
This page was built for publication: Steiner trees, partial 2–trees, and minimum IFI networks