Title :
Finding spanning trees and Hamiltonian circuits in an un-oriented graph an algebraic approach
Author :
Onete, Cristian E. ; Onete, A. Maria Cristina C
Author_Institution :
NXP Semicond., Eindhoven, Netherlands
Abstract :
In this paper, symbolic matrices and a simple algebraic method to list spanning trees and find Hamiltonian circuits in a simple un-oriented graph are used. A concrete, fully-parallel algorithm that achieves both goals, with examples is shown. A necessary and sufficient condition for Hamiltonicity is presented, too.
Keywords :
algebra; network analysis; trees (electrical); Hamiltonian circuits; Hamiltonicity; algebraic approach; fully-parallel algorithm; spanning trees; unoriented graph; Admittance; Algebra; Complexity theory; Equations; Optimization; Runtime; Sufficient conditions; Graph theory; Hamiltonian circuit; Necessary and sufficient condition for Hamiltonicity; Spanning tree;
Conference_Titel :
Circuit Theory and Design (ECCTD), 2011 20th European Conference on
Conference_Location :
Linkoping
Print_ISBN :
978-1-4577-0617-2
Electronic_ISBN :
978-1-4577-0616-5
DOI :
10.1109/ECCTD.2011.6043384
