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

DOI10.1002/net.21923zbMath1528.68148WikidataQ126568023 ScholiaQ126568023MaRDI QIDQ6087398

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

Publication date: 15 November 2023

Published in: Networks (Search for Journal in Brave)

zbMATH Keywords

dynamic programmingtreewidthparameterized complexityFPT algorithmminimum-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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• On minimum reload cost cycle cover
• A simplified NP-complete satisfiability problem
• The minimum reload \(s-t\) path, trail and walk problems
• The complexity of a minimum reload cost diameter problem
• Treewidth. Computations and approximations
• Bin packing with fixed number of bins revisited
• Parameterized complexity of the MinCCA problem on graphs of bounded decomposability
• On the complexity of constructing minimum changeover cost arborescences
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Reload cost trees and network design
• On Minimum Changeover Cost Arborescences
• On minimum reload cost paths, tours, and flows
• Complexity of edge coloring with minimum reload/changeover costs
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized Algorithms
• Reload cost problems: Minimum diameter spanning tree
• Constructing minimum changeover cost arborescenses in bounded treewidth graphs