Plans for the module on Hamiltonian paths (cycles etc.)
More...
Go to the source code of this file.
Namespaces 
namespace  OKlib::HamiltonianPaths 
 Active clausesets to search for Hamiltonian paths etc.

namespace  OKlib 
 All components of the OKlibrary.

Detailed Description
Plans for the module on Hamiltonian paths (cycles etc.)
 Todo:
 Update namespaces.
 Todo:
 Create milestones.
 Todo:
 Given a graph G, the alliance expressing the Hamiltonian path (cycle) property has variables v_1, ..., v_n for n = V(G) with domains V(G), and two active clausesets:
 injectivity (bijectivity) for v_1, ..., v_n
 v_i, v_{i+1} must get adjacent vertices in G (if considering Hamiltonian cycles, then this wraps around); call this active clauseset the adjacency constraint.
This is a special case of graphembedding (embedding a path resp. a cycle).
 Todo:
 One could add "opportunistically" some elements of the bijectivity constraint to the adjacency constraint; for example if there are v_i and v_j such that the minimal distance between their possible values in G is larger than the distance between i and j, then the current partial assignment is unsatisfiable (an extreme case here is given by a disconnected G)  this inconsistency cannot be anticipated by any of the two active clausesets alone (but must be realised by the alliance). Is there a general method behind that, leading to a meaningfully strengthened adjacency constraint?! Perhaps it is better (this might also be true in general) to create new active clausesets capturing these constraints (for example a "distance constraint", maintaining that the minimal distance in G of the possible values of any two vertices v_i and v_j is not larger than the distance of i and j).
 Todo:
 Creating a catalogue with Hamiltonian graphs and nonHamiltonian graphs (for creating benchmarks).
 Todo:
 Are there competitions on the subject?
 Todo:
 The Hamiltonian Path/Cycle problem is a special case of the graph embedding problem: The adjacency constraint just has to consider a general graph G_0 with vertices v_1, ..., v_n instead of the path resp. cycle on v_1, ..., v_n. One needs good data structures for the adjacency constraint.
 Todo:
 The graph isomorphism problem (see module Isomorphisms) is a special case of the graph embedding problem: How do graph embedding algorithms perform on graph isomorphism problems?
 Todo:
 TSP
Definition in file general.hpp.