On the parallel complexity of the alternating Hamiltonian cycle problem

DOI10.1007/3-540-61576-8_96MaRDI QIDQ6567696zbMATH OpenFDO

Authors Evripidis Bampis, Y. Manoussakis, Ioannis Milis

Publication date 5 July 2024

Full work available at URL https://doi.org/10.1007/3-540-61576-8_96

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• On the parallel complexity of the alternating Hamiltonian cycle problem
• Hamiltonian problems in edge-colored complete graphs and eulerian cycles in edge-colored graphs : some complexity results
• Finding a Longest Alternating Cycle in a 2-edge-coloured Complete Graph is in RP
• scientific article; zbMATH DE number 718675
• Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs

Cites work

• A Parallel Reduction of Hamiltonian Cycle to Hamiltonian Path in Tournaments
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• Alternating Hamiltonian cycles
• An improved parallel algorithm for maximal matching
• Cycles and paths in bipartite tournaments with spanning configurations
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• Graph folding and programmable logic array
• Graphs with Hamiltonian cycles having adjacent lines different colours
• Hamiltonian circuits determining the order of chromosomes
• scientific article; zbMATH DE number 4049453 (Why is no real title available?)
• scientific article; zbMATH DE number 3257168 (Why is no real title available?)
• Matching is as easy as matrix inversion
• Paths, Trees, and Flowers
• Sorting, Minimal Feedback Sets, and Hamilton Paths in Tournaments
• The Parallel Evaluation of General Arithmetic Expressions

This page was built for publication: On the parallel complexity of the alternating Hamiltonian cycle problem

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