Parallel connectivity in edge-colored complete graphs: complexity results

DOI10.1007/s00373-023-02747-4OpenAlexW4391716630MaRDI QIDQ6154375

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

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Links in edge-colored graphs
• Alternating Hamiltonian cycles
• Hamiltonian circuits determining the order of chromosomes
• 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
• The number of 2-edge-colored complete graphs with unique Hamiltonian alternating cycle
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• Maximum colored trees in edge-colored graphs
• Paths and trails in edge-colored graphs
• Cycles and paths in edge‐colored graphs with given degrees
• Graph folding and programmable logic array
• On the Computational Complexity of Combinatorial Problems
• On the Complexity of Timetable and Multicommodity Flow Problems
• Color-coding
• Finding a Longest Alternating Cycle in a 2-edge-coloured Complete Graph is in RP
• 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