All Questions
7 questions
1
vote
0
answers
45
views
Vertex cover via maximally unbalanced spanning trees
The vertex cover problem asks for a smallest subset $U\subseteq V$ that is adjacent to all edges of a symmetric graph $G(V,E)$.
Inspired by the observation that led to this question Perfectly balanced ...
- 13.2k
2
votes
1
answer
138
views
Generating short Hamilton cycles from complete graphs
Let $G(V,E)$ be a complete symmetric graph without self-loops or parallel edges; depending on the context the edges may however be interpreted as a pair of antiparallel arcs of equal weight.
A vertex ...
- 13.2k
0
votes
0
answers
55
views
Does LKH perform best with $\mathrm{1\unicode{x2013}trees}$
The LKH heuristic essentially generates sequence connected graphs with $n$ edges by means calculating minimum-weight spanning trees of $n-1$ of the vertices and connects the unspanned vertex to the ...
- 13.2k
0
votes
0
answers
26
views
Complexity of heaviest 2-optimal vertex-disjoint cycle covers
Calculating lightest vertex-disjoint cycle covers of finite complete symmetric graphs with weighted edges can be done efficiently and also renders the edge set of the calculated cycles free of pairs ...
- 13.2k
1
vote
0
answers
33
views
Calculating vertex weights via mutually tangent circles of triangles
given a metric graph with positive edge weights $\left|e_{ij}\right|$ a standard task, especially in the context of the Traveling Salesman Problem, is to calculate $\max\sum\limits_{i=1}^n\omega_i:\ \...
- 13.2k
-2
votes
1
answer
174
views
What is known about iterated matching as a TSP heuristic
A fairly wellknown heuristic for TSP that is based on matching is described in the 2003 paper Match twice and stitch: a new TSP tour construction heuristic by Andrew B. Kahng and Sherief Reda.
Its ...
- 13.2k
0
votes
0
answers
37
views
Generating Biconnected Graphs from Spanning Trees
Background of my question is an idea for generating an initial subtour for general symmetric TSPs:
Add to a MST a set of edges with minimal weight sum, that renders the resulting graph free of ...
- 13.2k