The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles

DOI10.1016/j.tcs.2015.08.016zbMath1330.05065OpenAlexW1639261090MaRDI QIDQ497683

Laurent Gourvès, Carlos A. Martinhon, Luérbio Faria, Jérôme Monnot

Publication date: 25 September 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.08.016

zbMATH Keywords

monochromatic pathsedge-colored graphsedge-recoloring costproperly edge-colored pathstrails and cycles

Mathematics Subject Classification ID

Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of minimum convex coloring
• A matrix-based approach to searching colored paths in a weighted colored multidigraph
• A simplified NP-complete satisfiability problem
• Convex recolorings of strings and trees: Definitions, hardness results and algorithms
• Using matrices to link conflict evolution and resolution in a graph model
• On monochromatic paths in m-coloured tournaments
• On monochromatic paths in edge-coloured digraphs
• A note on alternating cycles in edge-coloured graphs
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• Complexity of trails, paths and circuits in arc-colored digraphs
• Paths and trails in edge-colored graphs
• Hardness and inapproximability of convex recoloring problems
• Convex recoloring of paths
• Partial convex recolorings of trees and galled networks
• Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems
• Approximation Schemes for the Restricted Shortest Path Problem
• Convex Recoloring Revisited: Complexity and Exact Algorithms

This page was built for publication: The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles