[1902.10337] Deterministic "Snakes and Ladders" Heuristic for the Hami...
source link: https://arxiv.org/abs/1902.10337
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Submitted on 27 Feb 2019]
Deterministic "Snakes and Ladders" Heuristic for the Hamiltonian Cycle Problem
We present a polynomial complexity, deterministic, heuristic for solving the Hamiltonian Cycle Problem (HCP) in an undirected graph of order n. Although finding a Hamiltonian cycle is not theoretically guaranteed, we have observed that the heuristic is successful even in cases where such cycles are extremely rare, and it also performs very well on all HCP instances of large graphs listed on the TSPLIB web page. The heuristic owes its name to a visualisation of its iterations. All vertices of the graph are placed on a given circle in some order. The graph's edges are classified as either snakes or ladders, with snakes forming arcs of the circle and ladders forming its chords. The heuristic strives to place exactly n snakes on the circle, thereby forming a Hamiltonian cycle. The Snakes and Ladders Heuristic (SLH) uses transformations inspired by k−opt algorithms such as the, now classical, Lin-Kernighan heuristic to reorder the vertices on the circle in order to transform some ladders into snakes and vice versa. The use of a suitable stopping criterion ensures the heuristic terminates in polynomial time if no improvement is made in n3 major iterations.
| Subjects: | Combinatorics (math.CO); Discrete Mathematics (cs.DM) |
| Cite as: | arXiv:1902.10337 [math.CO] |
| (or arXiv:1902.10337v1 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.1902.10337 | |
| Journal reference: | Mathematical Programming Computation 6(1), 55-75, 2014 |
Recommend
-
20
Software developers downloading a seemingly innocent software library could find themselves hemorrhaging Bitcoin thanks to a wily atta...
-
26
Analysis of Chutes and Ladders Have you ever played the game Chutes and Ladders® ? In England, where I grew...
-
9
Snakes in a Facebook Datacenter Tuesday, September 22, 2020 at...
-
17
Super Snakes Have you ever been confused by the __underscores__ required by some of __RUBY__'s features? You can get i...
-
9
Want Business Agility? Rethink Your Easy Career Ladders, Part 4 You want business agility. The teams have worked hard to change how they work. And you realize your
-
3
Product Management Career Ladders at 8 Top Technology Firms Slides: Product Management Career Ladders by Sachin Rekhi, Founder...
-
8
Radioactive Rat Snakes Could Help Monitor Fukushima FalloutScientists have attached dosimeters to the reptiles so they can serve as living “bioindicators” to gauge contamination levels near the shuttered n...
-
3
15 Sep 2021 1:02 am AESTDate TimeModern snakes evolved from few survivors of dino-killing asteroidUniversity of BathA new study suggests that all living snakes evolved from a...
-
8
Developing employees Stop Offering Career Ladders. Start Offering Career Portfolios.
-
4
Why design skill maps are not inclusive career laddersLet go of the skills obsession to humanize career progressionI remember the first time I asked my manager for a promot...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK