Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem

DOI10.1016/J.JDA.2014.11.005MaRDI QIDQ2253903zbMATH OpenOpenAlexFDO

Authors Tibor Jordán, Ildikó Schlotter

Publication date 13 February 2015

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2014.11.005

zbMATH Keywords

network designparameterized complexitySteiner foresttree-width

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The path restoration version of the spare capacity allocation problem with modularity restrictions: models, algorithms, and an empirical analysis
• On the complexity of the regenerator location problem -- treewidth and other parameters (extended abstract)
• On the complexity of the regenerator location problem treewidth and other parameters
• Economic spare capacity planning for DCS mesh-restorable networks
• On the edge capacitated Steiner tree problem

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Applying tabu search to spare capacity planning for network restoration
• Complexity of Finding Embeddings in a k-Tree
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Fourier meets M\"{o}bius: fast subset convolution
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1361465 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Improved Steiner tree algorithms for bounded treewidth
• On multiple steiner subgraph problems
• On Recursions Connected With Symmetric Groups I
• On the Complexity of Timetable and Multicommodity Flow Problems
• Parametrized complexity theory.
• Solving min-max shortest-path problems on a network
• Steiner problem in networks: A survey
• The Complexity of Multiterminal Cuts
• The Rectilinear Steiner Tree Problem is NP-Complete
• The Steiner forest problem revisited
• The steiner problem in graphs
• Treewidth. Computations and approximations
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

This page was built for publication: Parameterized complexity of spare capacity allocation and the multicost Steiner subgraph problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2253903)