Refined parameterizations for computing colored cuts in edge-colored graphs
From MaRDI portal
Publication:2082563
DOI10.1007/s00224-022-10101-zOpenAlexW4296900537MaRDI QIDQ2082563
Christian Komusiewicz, Frank Sommer, Nils Morawietz, Niels Grüttemeier
Publication date: 4 October 2022
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-022-10101-z
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) 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
- The label cut problem with respect to path length and label frequency
- Fundamentals of parameterized complexity
- The disjoint paths problem in quadratic time
- Approximation and hardness results for label cut and related problems
- Approximating the minimal sensor selection for supervisory control
- Which problems have strongly exponential complexity?
- Edge-colored graphs with applications to homogeneous faults
- The parameterized complexity of some minimum label problems
- Parametrized complexity theory.
- Refined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs
- Kernelization Lower Bounds Through Colors and IDs
- On Problems as Hard as CNF-SAT
- Parameterized Algorithms
- Graph-Theoretic Concepts in Computer Science
- Optimal Listing of Cycles and st-Paths in Undirected Graphs
- New algorithms for the minimum coloring cut problem
This page was built for publication: Refined parameterizations for computing colored cuts in edge-colored graphs
