scientific article; zbMATH DE number 7205187

DOI10.4230/LIPIcs.IPEC.2017.3zbMath1443.68119arXiv1703.01686MaRDI QIDQ5111862

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

dynamic programmingtreewidthparameterized complexityFPT algorithmminimum-diameter spanning treereload-cost problems

Mathematics Subject Classification ID

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)

Related Items (1)

A unifying model for locally constrained spanning tree problems

Cites Work

• 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
• 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
• Reload cost problems: Minimum diameter spanning tree
• Constructing minimum changeover cost arborescenses in bounded treewidth graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: