publication . Other literature type . Article . 2006

SOLVING THE HAMILTONIAN CYCLE PROBLEM USING SYMBOLIC DETERMINANTS

Vladimir Ejov; Filar, Ja; Lucas, Sk; Nelson, Jl;
Open Access English
  • Published: 01 Feb 2006
  • Publisher: Mathematical Society of the Republic of China
  • Country: United States
Abstract
In this note we show how the Hamiltonian Cycle problem can be reduced to solving a system of polynomial equations related to the adjacency matrix of a graph. This system of equations can be solved using the method of Gr¨obner bases, but we also show how a symbolic determinant related to the adjacency matrix can be used to directly decide whether a graph has a Hamiltonian cycle.
Subjects
arXiv: Computer Science::Databases
free text keywords: Numerical Analysis, Real and Complex Functions (incl Several Variables), Hamiltonian cycle, Gröbner bases, symbolic algebra, 05C45, 13P10, 68W30, 68R10, Adjacency matrix, Mathematical analysis, Topology, System of polynomial equations, Mathematics, Symbolic computation, System of linear equations, Hamiltonian path problem, Markov decision process, Hamiltonian path, symbols.namesake, symbols, Graph energy, Algebra, Discrete mathematics
Related Organizations
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Other literature type . Article . 2006

SOLVING THE HAMILTONIAN CYCLE PROBLEM USING SYMBOLIC DETERMINANTS

Vladimir Ejov; Filar, Ja; Lucas, Sk; Nelson, Jl;