Parallel connectivity in edge-colored complete graphs: complexity results

DOI10.1007/S00373-023-02747-4MaRDI QIDQ6154375zbMATH OpenOpenAlexFDO

Authors Rachid Saad

Publication date 15 February 2024

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00373-023-02747-4

zbMATH Keywords

approximationEulerian subgraphsedge-colored complete graphsparallel connectivity

Mathematics Subject Classification ID

Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Recommendations

• Paths and trails in edge-colored graphs
• Alternating paths in edge-colored complete graphs
• Paths and Trails in Edge-Colored Graphs
• On the maximum disjoint paths problem on edge-colored graphs
• Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity results

Cites work

• 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?)
• Alternating Hamiltonian cycles
• Alternating cycles and paths in edge-coloured multigraphs: A survey
• Alternating cycles and trails in \(2\)-edge-coloured complete multigraphs
• Alternating paths in edge-colored complete graphs
• Color-coding
• Cycles and paths in edge‐colored graphs with given degrees
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• Finding a Longest Alternating Cycle in a 2-edge-coloured Complete Graph is in RP
• Graph folding and programmable logic array
• Hamiltonian circuits determining the order of chromosomes
• Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity results
• Links in edge-colored graphs
• Maximum colored trees in edge-colored graphs
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the Computational Complexity of Combinatorial Problems
• Paths and trails in edge-colored graphs
• The number of 2-edge-colored complete graphs with unique Hamiltonian alternating cycle

This page was built for publication: Parallel connectivity in edge-colored complete graphs: complexity results

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