On the parallel complexity of the alternating Hamiltonian cycle problem

DOI10.1051/RO:1999119MaRDI QIDQ4497876zbMATH OpenOpenAlexFDO

Authors Ioannis Milis, Evripidis Bampis, Y. Manoussakis

Publication date 24 August 2000

Published in RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=RO_1999__33_4_421_0/, https://eudml.org/doc/197799

zbMATH Keywords

graph with colored edgesHamiltonian cycle

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 718675
• Finding a Longest Alternating Cycle in a 2-edge-coloured Complete Graph is in RP
• Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs

Cited in

(7)

• The parity Hamiltonian cycle problem
• A space-efficient parameterized algorithm for the Hamiltonian Cycle problem by dynamic algebraization
• The parity Hamiltonian cycle problem in directed graphs
• On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs
• 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
• On the parallel complexity of the alternating Hamiltonian cycle problem

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 Q4497876)