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.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The control flow of programs can be represented by directed graphs. In this paper we provide a uniform and detailed formal basis for control flow graphs combining known definitions and results with new aspects. Two graph reductions are defined using only syntactical information about the graphs, but no semantical information about the represented programs. We prove some properties of reduced graphs and also about the paths in reduced graphs. Based on graphs, we define statement coverage and branch coverage such that coverage notions correspond to node coverage, and edge coverage, respectively.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.