On the parallel complexity of the alternating Hamiltonian cycle problem
From MaRDI portal
Publication:6567696
DOI10.1007/3-540-61576-8_96zbMATH Open1543.68265MaRDI QIDQ6567696FDOQ6567696
Authors: Evripidis Bampis, Y. Manoussakis, Ioannis Milis 
Publication date: 5 July 2024
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45) Parallel algorithms in computer science (68W10)
Cites Work
- Paths, Trees, and Flowers
- Cycles and paths in bipartite tournaments with spanning configurations
- A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
- An improved parallel algorithm for maximal matching
- Matching is as easy as matrix inversion
- DNA physical mapping and alternating Eulerian cycles in colored graphs
- The Parallel Evaluation of General Arithmetic Expressions
- Graph folding and programmable logic array
- Hamiltonian circuits determining the order of chromosomes
- Title not available (Why is that?)
- Alternating Hamiltonian cycles
- Graphs with Hamiltonian cycles having adjacent lines different colours
- Sorting, Minimal Feedback Sets, and Hamilton Paths in Tournaments
- Title not available (Why is that?)
- A Parallel Reduction of Hamiltonian Cycle to Hamiltonian Path in Tournaments
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)
