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

connectivityEdge colored graphsproperly edge-colored pathstrails and cycles

Mathematics Subject Classification ID

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

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

• 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
• 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?)
• 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)

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

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)