» ASP Competition | |
|
Hamiltonian PathProblem descriptionA Hamiltonian Path (or HP for short) in a directed graph G = (V,E), where V is the set of vertices and E is the set of edges, is a path in G such that every vertex v in V occurs exactly once in the path. The input of the HP problem is a directed graph. The goal is to find an HP in the graph. Input formatA directed input graph is represented by the following predicates: a.
The vertices of the input graph are given by instances of "vtx" as follows: b.
The edges of the graph are given by instances of "edge" as follows: c.
Finally, exactly one instance of "start" specifies the first vertex of the HP: For further illustration, compare the instances available at asparagus. Output formatA solution is represented by means of a binary predicate "path" such that each instance of "path" corresponds to an edge. The edges in "path" must be the ones of some HP in the input graph. Author: Lengning Liu, Miroslaw Truszczynski, and Martin Gebser |