Paths and Trails in Edge-Colored Graphs

DOI10.1007/978-3-540-78773-0_62MaRDI QIDQ5458574zbMATH OpenOpenAlexFDO

Authors

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) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Connectivity (05C40)

Recommendations

• Paths and trails in edge-colored graphs
• On \(s\)--\(t\) paths and trails in edge-colored graphs
• On paths, trails and closed trails in edge-colored graphs
• Paths and trails in edge-colored weighted graphs
• Complexity of Paths, Trails and Circuits in Arc-Colored Digraphs

Cites work

• scientific article; zbMATH DE number 432790 (Why is no real title available?)
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 4049453 (Why is no real title available?)
• scientific article; zbMATH DE number 1557065 (Why is no real title available?)
• scientific article; zbMATH DE number 1764950 (Why is no real title available?)
• scientific article; zbMATH DE number 758733 (Why is no real title available?)
• A note on alternating cycles in edge-coloured graphs
• Alternating cycles and paths in edge-coloured multigraphs: A survey
• Alternating cycles in edge-partitioned graphs
• Alternating paths in edge-colored complete graphs
• Characterization of edge-colored complete graphs with properly colored Hamilton paths
• Faster scaling algorithms for general graph matching problems
• Finding a Longest Alternating Cycle in a 2-edge-coloured Complete Graph is in RP
• Finding paths in graphs avoiding forbidden transitions
• Hamiltonian circuits determining the order of chromosomes
• 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
• On the Computational Complexity of Combinatorial Problems
• Paths and Trails in Edge-Colored Graphs
• The directed subgraph homeomorphism problem
• The number of 2-edge-colored complete graphs with unique Hamiltonian alternating cycle

Cited in

(19)

• Paths and Trails in Edge-Colored Graphs
• Paths through K-specified edges in a linear graph
• Trails in arc-colored digraphs avoiding forbidden transitions
• On paths, trails and closed trails in edge-colored graphs
• The edge-recoloring cost of paths and cycles in edge-colored graphs and digraphs
• Complexity of trails, paths and circuits in arc-colored digraphs
• Maximum disjoint paths on edge-colored graphs: approximability and tractability
• Paths and trails in edge-colored weighted graphs
• On the complexity of path problems in properly colored directed graphs
• On the tractability of shortest path problems in weighted edge-coloured graphs
• Symbolic coloured SCC decomposition
• Paths and trails in edge-colored graphs
• On \(s\)--\(t\) paths and trails in edge-colored graphs
• Parallel connectivity in edge-colored complete graphs: complexity results
• On the maximum disjoint paths problem on edge-colored graphs
• Acyclicity in edge-colored graphs
• Complexity of Paths, Trails and Circuits in Arc-Colored Digraphs
• scientific article; zbMATH DE number 762736 (Why is no real title available?)
• Properly coloured cycles and paths: Results and open problems

This page was built for publication: Paths and Trails in Edge-Colored Graphs

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