Affiliations: Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland and Institute of Bioorganic Chemistry, Polish Academy of Sciences, Poznan, Poland, [email protected]
Note: [] Address for correspondence: Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznan, Poland
Abstract: The results presented in the paper are threefold. Firstly, a new class of reduced-by-matching directed graphs is defined and its properties studied. The graphs are output from the algorithm which, for a given 1-graph, removes arcs which are unnecessary from the point of view of searching for a Hamiltonian circuit. In the best case, the graph is reduced to a quasi-adjoint graph, what results in polynomial-time solution of the Hamiltonian circuit problem. Secondly, the systematization of several classes of digraphs, known from the literature and referring to directed line graphs, is provided together with the proof of its correctness. Finally, computational experiments are presented in order to verify the effectiveness of the reduction algorithm.
