Complexity of Paths, Trails and Circuits in Arc-Colored Digraphs

DOI10.1007/978-3-642-13562-0_21MaRDI QIDQ3569078zbMATH OpenOpenAlexFDO

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

Publication date 17 June 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://basepub.dauphine.fr/handle/123456789/4450

zbMATH Keywords

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

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Complexity of trails, paths and circuits in arc-colored digraphs
• scientific article; zbMATH DE number 5238183
• Paths, cycles, and arc‐connectivity in digraphs
• On the Complexity of Colouring by Vertex-Transitive and Arc-Transitive Digraphs
• scientific article; zbMATH DE number 4198025
• Paths, cycles and circular colorings in digraphs
• The complexity of arc-colorings for directed hypergraphs
• The complexity of arc-colorings for directed hypergraphs
• Paths and trails in edge-colored graphs
• Paths and Trails in Edge-Colored Graphs

Cited in

(7)

• Paths and Trails in Edge-Colored Graphs
• Trails in arc-colored digraphs avoiding forbidden transitions
• On paths, trails and closed trails in edge-colored graphs
• Complexity of trails, paths and circuits in arc-colored digraphs
• On the complexity of path problems in properly colored directed graphs
• On the complexity of the colorful directed paths in vertex coloring of digraphs
• A note on testing axioms of revealed preference

This page was built for publication: Complexity of Paths, Trails and Circuits in Arc-Colored Digraphs

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