Minimum reload cost graph factors
DOI10.1007/s00224-020-10012-xzbMath1469.05155arXiv1810.11700OpenAlexW2964198134MaRDI QIDQ5918369
Mordechai Shalom, Didem Gözüpek, Dimitrios M. Thilikos, Julien Baste
Publication date: 5 August 2021
Published in: Theory of Computing Systems, SOFSEM 2019: Theory and Practice of Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1810.11700
Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (1)
Cites Work
- Unnamed Item
- Fundamentals of parameterized complexity
- On minimum reload cost cycle cover
- Mixed searching and proper-path-width
- Separating subgraphs in k-trees: Cables and caterpillars
- The minimum reload \(s-t\) path, trail and walk problems
- An algorithm for computing simple \(k\)-factors
- The complexity of a minimum reload cost diameter problem
- Treewidth. Computations and approximations
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- 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
- Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
- Complexity of edge coloring with minimum reload/changeover costs
- The complexity of satisfiability problems
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized Algorithms
- Tree-decompositions of small pathwidth
- Reload cost problems: Minimum diameter spanning tree
- Constructing minimum changeover cost arborescenses in bounded treewidth graphs
This page was built for publication: Minimum reload cost graph factors
