Refined parameterizations for computing colored cuts in edge-colored graphs

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

zbMATH Keywords

fixed-parameter tractabilitykernelizationnetwork robustnesslabeled cut

Mathematics Subject Classification ID

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