Paths and Trails in Edge-Colored Graphs

DOI10.1007/978-3-540-78773-0_62zbMath1136.68445OpenAlexW1878594033MaRDI QIDQ5458574

No author found.

Publication date: 15 April 2008

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

Full work available at URL: https://doi.org/10.1007/978-3-540-78773-0_62

zbMATH Keywords

connectivityproperly edge-colored pathstrails and cyclesEdge colored graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Related Items

Symbolic coloured SCC decomposition ⋮ Paths and Trails in Edge-Colored Graphs ⋮ Properly Coloured Cycles and Paths: Results and Open Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The directed subgraph homeomorphism problem
• Alternating cycles in edge-partitioned graphs
• Hamiltonian circuits determining the order of chromosomes
• A note on alternating cycles in edge-coloured graphs
• Alternating cycles and paths in edge-coloured multigraphs: A survey
• Alternating paths in edge-colored complete graphs
• Finding paths in graphs avoiding forbidden transitions
• The number of 2-edge-colored complete graphs with unique Hamiltonian alternating cycle
• Characterization of edge-colored complete graphs with properly colored Hamilton paths
• On the Computational Complexity of Combinatorial Problems
• Faster scaling algorithms for general graph matching problems
• Finding a Longest Alternating Cycle in a 2-edge-coloured Complete Graph is in RP
• Paths and Trails in Edge-Colored Graphs
• Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity results
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems