The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles
From MaRDI portal
Publication:497683
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
monochromatic pathsedge-colored graphsedge-recoloring costproperly edge-colored pathstrails and cycles
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
