Refined parameterizations for computing colored cuts in edge-colored graphs

DOI10.1007/978-3-030-38919-2_21MaRDI QIDQ3297773zbMATH OpenOpenAlexFDO

Authors Nils Morawietz, Niels Grüttemeier, Christian Komusiewicz, Frank Sommer

Publication date 20 July 2020

Published in SOFSEM 2020: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-38919-2_21

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Cutting up is hard to do: the parameterised complexity of k-cut and related problems
• Maximum disjoint paths on edge-colored graphs: approximability and tractability
• On the parameterized complexity of colorful components and related problems

Cites work

• Combinatorial optimization in networks with shared risk link groups
• Edge-colored graphs with applications to homogeneous faults
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 2150800 (Why is no real title available?)
• Parameterized algorithms
• The label cut problem with respect to path length and label frequency
• The parameterized complexity of some minimum label problems

Cited in

(5)

• Refined parameterizations for computing colored cuts in edge-colored graphs
• Colored cut games
• Computing the chromatic number using graph decompositions via matrix rank
• Destroying Multicolored Paths and Cycles in Edge-Colored Graphs
• Colored cut games

This page was built for publication: Refined parameterizations for computing colored cuts in edge-colored graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3297773)