The parity Hamiltonian cycle problem in directed graphs

DOI10.1007/978-3-319-45587-7_5MaRDI QIDQ2835661zbMATH OpenOpenAlexFDO

Authors Hiroshi Nishiyama, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita

Publication date 30 November 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-45587-7_5

zbMATH Keywords

\(T\)-joinsHamiltonian cyclelinear system over GF(2)

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Recommendations

• The parity Hamiltonian cycle problem
• On the parallel complexity of the alternating Hamiltonian cycle problem
• Parity Subgraph, Shortest Cycle Cover, and Postman Tour
• General models for variations of the even cycle problem
• The parity path problem on some subclasses of perfect graphs

Cites work

• Balanced group-labeled graphs
• Characterization of even directed graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial optimization. Theory and algorithms.
• Exponential lower bounds for polytopes in combinatorial optimization
• Expressing combinatorial optimization problems by linear programs
• Finding 2-factors closer to TSP tours in cubic graphs
• scientific article; zbMATH DE number 3957111 (Why is no real title available?)
• scientific article; zbMATH DE number 1498519 (Why is no real title available?)
• Linear vs. semidefinite extended formulations
• Maximum Cardinality Simple 2-matchings in Subcubic Graphs
• Polynomials associated with nowhere-zero flows
• TSP on cubic and subcubic graphs

Cited in

(2)

• A note on the Hamiltonian circuit problem on directed path graphs
• The parity Hamiltonian cycle problem

This page was built for publication: The parity Hamiltonian cycle problem in directed graphs

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