Parameterized complexity of finding a spanning tree with minimum reload cost diameter
DOI10.4230/LIPICS.IPEC.2017.3zbMATH Open1443.68119arXiv1703.01686MaRDI QIDQ5111862FDOQ5111862
Dimitrios M. Thilikos, Julien Baste, Mordechai Shalom, Christophe Paul, Ignasi Sau, Didem Gözüpek
Publication date: 27 May 2020
Full work available at URL: https://arxiv.org/abs/1703.01686
Recommendations
dynamic programmingtreewidthFPT algorithmparameterized complexityminimum-diameter spanning treereload-cost problems
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
- Graph theory
- Title not available (Why is that?)
- Title not available (Why is that?)
- A simplified NP-complete satisfiability problem
- On minimum reload cost paths, tours, and flows
- On minimum reload cost cycle cover
- Bin packing with fixed number of bins revisited
- The complexity of a minimum reload cost diameter problem
- On Minimum Changeover Cost Arborescences
- A \(c^k n\) 5-approximation algorithm for treewidth
- Reload cost trees and network design
- Reload cost problems: Minimum diameter spanning tree
- The minimum reload \(s-t\) path, trail and walk problems
- Complexity of edge coloring with minimum reload/changeover costs
- Parameterized complexity of the MinCCA problem on graphs of bounded decomposability
- On the complexity of constructing minimum changeover cost arborescences
- Constructing minimum changeover cost arborescenses in bounded treewidth graphs
Cited In (5)
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 Q5111862)
