scientific article; zbMATH DE number 88947

MaRDI QIDQ4016524zbMATH OpenFDO

Authors Iain Stewart

Publication date 16 January 1993

zbMATH Keywords

digraphdirected Hamiltonian pathHamiltonian path operatorNPprojection translations

Mathematics Subject Classification ID

Other classical first-order model theory (03C68) Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Using the Hamiltonian path operator to capture NP
• scientific article; zbMATH DE number 139797
• The edge Hamiltonian path problem is NP-complete for bipartite graphs
• Complete problems for monotone NP
• A note on the Hamiltonian circuit problem on directed path graphs

Cited in

(4)

• Using the Hamiltonian path operator to capture NP
• Comparing the Expressibility of Languages Formed Using NP-Complete Operators
• scientific article; zbMATH DE number 139797 (Why is no real title available?)
• Methods for proving completeness via logical reductions

This page was built for publication:

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