Questions tagged [hamiltonian-path]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
John D's user avatar
  • 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 ...
A.Omidi's user avatar
  • 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 ...
Optimization team's user avatar
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 ...
Daniele Cuomo's user avatar
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), ...
Michaël's user avatar
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?
DSPinfinity's user avatar
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 ...
DSPinfinity's user avatar