Steiner trees, partial 2–trees, and minimum IFI networks

From MaRDI portal
Revision as of 12:21, 4 February 2024 by Import240129110113 (talk | contribs) (Created automatically from import240129110113)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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




Related Items (84)

Perfect edge domination and efficient edge domination in graphsArborescence polytopes for series-parallel graphsThe Steiner tree problem. I: Formulations, compositions and extensions and extension of facetsThe Steiner tree problem. II: Properties and classes of facetsComputing directed Steiner path coversHeuristics for the network design problem with connectivity requirementsCharacterization of partial 3-trees in terms of three structuresA stronger lower bound on parametric minimum spanning treesA column generation approach for solving a non-temporal forest harvest model with spatial structure constraintsSteiner problem in Halin networksCanonical representations of partial 2-and 3-treesMinimum-maximal matching in series-parallel graphsGeneration of polynomial-time algorithms for some optimization problems on tree-decomposable graphsCharacterization and Recognition of Partial 3-TreesA parallelizable lexicographically first maximal edge-induced subgraph problemCuts, matrix completions and graph rigidityLocally connected spanning trees in strongly chordal graphs and proper circular-arc graphsConstructive linear time algorithms for branchwidthThe monadic second-order logic of graphs III : tree-decompositions, minors and complexity issuesComplexity of Finding Embeddings in a k-TreeStructural conditions for cycle completable graphsLocally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphsA factoring approach for the Steiner tree problem in undirected networksOptimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral resultsIntersecting longest pathsCharacterizing graphs of maximum matching width at most 2Homomorphism bounds of signed bipartite \(K_4\)-minor-free graphs and edge-colorings of \(2k\)-regular \(K_4\)-minor-free multigraphsA simple linear time algorithm for triangulating three-colored graphsImproved Steiner tree algorithms for bounded treewidthToughness and spanning trees in K4‐minor‐free graphsRisk models for the prize collecting Steiner tree problems with interval dataP versus NPC: minimum Steiner trees in convex split graphsOn convexity in split graphs: complexity of Steiner tree and dominationA PTAS for weight constrained Steiner trees in series--parallel graphs.The complexity of the locally connected spanning tree problemOn the area of constrained polygonal linkagesForbidden minors characterization of partial 3-treesOn two dual classes of planar graphsOn the extension of a partial metric to a tree metricMinimum size tree-decompositionsNetwork ResiliencePermutation graphs: Connected domination and Steiner treesConcepts of signed graph coloringStronger MIP formulations for the Steiner forest problemAlgorithms for recognition of regular properties and decomposition of recursive graph familiesThe role of Steiner hulls in the solution to Steiner tree problemsTemporal constraint networksA stronger lower bound on parametric minimum spanning treesA note on integral generalized flows in directed partial 2-treesProblems with generalized Steiner problemsCharacterization and complexity of uniformly nonprimitive labeled 2-structuresMinimum size tree-decompositionsA technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-pathsCanonical representations of partial 2- and 3-treesThe most vital edges with respect to the number of spanning trees in two- terminal series-parallel graphsEfficient sets in partial \(k\)-treesOn the SPANNING \(k\)-TREE problemComputing residual connectedness reliability for restricted networksMinimum perfect bipartite matchings and spanning trees under categorizationTree decomposition and discrete optimization problems: a surveyAn O\((nm)\) algorithm for a special case of the multimedian location problem on a treeSteiner trees and polyhedraUsing a hybrid of exact and genetic algorithms to design survivable networksComplexity of Steiner Tree in Split Graphs - Dichotomy ResultsCycle stochastic graphs: Structural and forbidden graph characterizationsAssortment optimization under the multinomial logit model with product synergiesBounds on vertex colorings with restrictions on the union of color classesWeighted connected domination and Steiner trees in distance-hereditary graphsFinding a Small Number of Colourful ComponentsA linear time algorithm for computing the most reliable source on a series--parallel graph with unreliable edgesMULTI-TERMINAL NETWORK CONNECTEDNESS ON SERIES-PARALLEL NETWORKSThe graphs for which the maximum multiplicity of an eigenvalue is twoRevising Johnson's table for the 21st centuryAlgorithms for the clique problem with multiple-choice constraints under a series-parallel dependency graphThe traveling salesman problem on a graph and some related integer polyhedraPrimal-dual based distributed approximation algorithm for Prize-collecting Steiner treeSpeeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositionsEfficient algorithms for combinatorial problems on graphs with bounded decomposability - a surveySteiner's problem in double treesOn some optimization problems on \(k\)-trees and partial \(k\)-treesFinding maximum cliques in arbitrary and in special graphsThe Steiner tree polytope and related polyhedraTree polytope on 2-treesGeneralized Steiner problem in outerplanar networks




Cites Work




This page was built for publication: Steiner trees, partial 2–trees, and minimum IFI networks