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

DOI10.1016/J.TCS.2015.08.016MaRDI QIDQ497683zbMATH OpenOpenAlexFDO

Authors Laurent Gourvès, Carlos Martinhon, Luerbio 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

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

Recommendations

• The edge-recoloring cost of paths and cycles in edge-colored graphs and digraphs
• Properly colored paths and cycles in edge colored graphs
• Publication:4934405
• Complexity of edge coloring with minimum reload/changeover costs
• A generalization of properly colored paths and cycles in edge-colored graphs
• Partitioning edge-coloured complete graphs into monochromatic cycles and paths
• Properly coloured cycles and paths: Results and open problems
• A polyhedral approach to edge coloring
• Edge-coloring of multigraphs: Recoloring technique
• Monochromatic paths in 2-edge-coloured graphs and hypergraphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1557065 (Why is no real title available?)
• scientific article; zbMATH DE number 795216 (Why is no real title available?)
• A matrix-based approach to searching colored paths in a weighted colored multidigraph
• A note on alternating cycles in edge-coloured graphs
• A simplified NP-complete satisfiability problem
• Approximation Schemes for the Restricted Shortest Path Problem
• Complexity of trails, paths and circuits in arc-colored digraphs
• Convex Recoloring Revisited: Complexity and Exact Algorithms
• Convex recoloring of paths
• Convex recolorings of strings and trees: Definitions, hardness results and algorithms
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• Hardness and inapproximability of convex recoloring problems
• Network flows. Theory, algorithms, and applications.
• Networks, crowds and markets. Reasoning about a highly connected world.
• On monochromatic paths in edge-coloured digraphs
• On monochromatic paths in m-coloured tournaments
• On paths, trails and closed trails in edge-colored graphs
• Partial convex recolorings of trees and galled networks
• Paths and trails in edge-colored graphs
• Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems
• The complexity of minimum convex coloring
• Using matrices to link conflict evolution and resolution in a graph model

Cited in

(1)

• The edge-recoloring cost of paths and cycles in edge-colored graphs and digraphs

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

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