Parameterized complexity of finding a spanning tree with minimum reload cost diameter

DOI10.1002/NET.21923MaRDI QIDQ6087398zbMATH OpenWikidataFDO

Authors Julien Baste, Didem Gözüpek, Christophe Paul, Ignasi Sau, Mordechai Shalom, Dimitrios M. Thilikos

Publication date 15 November 2023

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/NET.21923

zbMATH Keywords

dynamic programmingtreewidthFPT algorithmparameterized complexityminimum-diameter spanning treereload-cost problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Parameterized complexity of finding a spanning tree with minimum reload cost diameter
• The complexity of a minimum reload cost diameter problem
• Reload cost problems: Minimum diameter spanning tree
• scientific article; zbMATH DE number 1420900

Cites work

• scientific article; zbMATH DE number 1634667 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 4121482 (Why is no real title available?)
• A c^k n 5-approximation algorithm for treewidth
• A simplified NP-complete satisfiability problem
• Bin packing with fixed number of bins revisited
• Complexity of edge coloring with minimum reload/changeover costs
• Constructing minimum changeover cost arborescenses in bounded treewidth graphs
• Fundamentals of parameterized complexity
• Graph theory
• On minimum changeover cost arborescences
• On minimum reload cost cycle cover
• On minimum reload cost paths, tours, and flows
• On the complexity of constructing minimum changeover cost arborescences
• Parameterized algorithms
• Reload cost problems: Minimum diameter spanning tree
• Reload cost trees and network design
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• The complexity of a minimum reload cost diameter problem
• The minimum reload \(s-t\) path, trail and walk problems
• Treewidth. Computations and approximations

Cited in

(1)

• On the complexity of the regenerator location problem treewidth and other parameters

This page was built for publication: Parameterized complexity of finding a spanning tree with minimum reload cost diameter

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