Packing Steiner trees with identical terminal sets

DOI10.1016/j.ipl.2004.03.006zbMath1192.68486OpenAlexW2095251431MaRDI QIDQ2390272

Petteri Kaski

Publication date: 21 July 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.03.006

zbMATH Keywords

computational complexitycombinatorial problemsNP-completenessSteiner tree packing

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Hardness and approximation results for packing Steiner trees ⋮ Steiner connectivity problems in hypergraphs ⋮ Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs ⋮ Packing trees in communication networks

Cites Work

• Geometric algorithms and combinatorial optimization.
• The Steiner tree packing problem in VLSI design
• Edge-disjoint trees containing some given vertices in a graph
• On decomposing a hypergraph into \(k\) connected sub-hypergraphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The complexity of satisfiability problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Packing Steiner trees with identical terminal sets