Complexity of trails, paths and circuits in arc-colored digraphs

DOI10.1016/j.dam.2012.10.025zbMath1262.05070OpenAlexW2155974074MaRDI QIDQ1946225

Jérôme Monnot, Adria Lyra, Laurent Gourvès, Carlos A. Martinhon

Publication date: 18 April 2013

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.10.025

zbMATH Keywords

NP-completenesspolynomial algorithmsarc-colored digraphsarc-colored tournamentsHamiltonian directed pathproperly arc-colored paths/trails and circuits

Mathematics Subject Classification ID

Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (6)

A System of Interaction and Structure III: The Complexity of BV and Pomset Logic ⋮ The complexity of routing problems in forbidden-transition graphs and edge-colored graphs ⋮ Unnamed Item ⋮ The edge-recoloring cost of monochromatic and properly edge-colored paths and cycles ⋮ Finding Paths in Grids with Forbidden Transitions ⋮ Paths and trails in edge-colored weighted graphs

This page was built for publication: Complexity of trails, paths and circuits in arc-colored digraphs