Questions tagged [hamiltonian-path]
The hamiltonian-path tag has no usage guidance.
7
questions
1
vote
1
answer
475
views
About circuit constraints in OR - tools
I am trying to implement a scheduling problem to solve with CP-SAT from OR-tools. There, in particular, for every machine I want to add a time transition constraint from every task that is performed ...
- 199
5
votes
2
answers
131
views
Number of simple cycles on the graph
I would like to know if there is an efficient way to formulate simple cycles on the Graph/Digraph. Let's say, there is a grid-form graph for which each vertex is only connected to a limited number of ...
- 8,505
3
votes
3
answers
189
views
Directed trees and the order/score of each node in the tree
Suppose we have a directed tree as follows:
The information regarding the edges are also given to us as a list
like edge_info = [ (a,c) , (a,b) , (b,d) , (b,e) , (b,f) ]
I am trying to find a way to ...
- 1,277
2
votes
0
answers
42
views
Shortest (undirected) path constrained to a sub-set of nodes
I expect this to be an NP-complete problem, as it may reduce to the Hamiltonian Path problem.
Anyway, I was wondering whether there exists some study and (aproximated) solutions for this particular ...
- 561
3
votes
2
answers
971
views
Simple example of finding Hamiltonian path using Google OR-Tools?
I'd like to test how good/fast OR-Tools is in finding hamiltonian paths on some (big) directed graphs.
But I can't find simple enough (for me) examples.
Something like these ones (or even simpler), ...
- 59
1
vote
1
answer
105
views
Equivalence of Shortest Hamiltonian Paths with a Starting Node to Traveling Salesman Problem
Q- Can someone explain the equivalence in detail please?
- 409
1
vote
1
answer
131
views
Equivalence of Shortest Hamiltonian Paths to Traveling Salesman Problem
Two questions:
Q1- Why do we need to add "bidirectional" arcs (instead of single directional arcs)
between the new node n + 1 and with every node in the original network?
Q2- Why is the ...
- 409