J. Blazewicz, M. Kasprzak
"Reduced-by-matching graphs: toward simplifying Hamiltonian circuit problem"
Fundamenta Informaticae
118 (2012) 225-244.
Download full text
— The final publication is available at IOS Press via
http://dx.doi.org/10.3233/FI-2012-711
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.
Back to the List of publications
12 Jul 2012