# Persistency in the Traveling Salesman Problem on Halin graphs

Discussiones Mathematicae Graph Theory (2000)

- Volume: 20, Issue: 2, page 231-242
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topVladimír Lacko. "Persistency in the Traveling Salesman Problem on Halin graphs." Discussiones Mathematicae Graph Theory 20.2 (2000): 231-242. <http://eudml.org/doc/270609>.

@article{VladimírLacko2000,

abstract = {For the Traveling Salesman Problem (TSP) on Halin graphs with three types of cost functions: sum, bottleneck and balanced and with arbitrary real edge costs we compute in polynomial time the persistency partition $E_\{All\}$, $E_\{Some\}$, $E_\{None\}$ of the edge set E, where:
$E_\{All\}$ = e ∈ E, e belongs to all optimum solutions,
$E_\{None\}$ = e ∈ E, e does not belong to any optimum solution and
$E_\{Some\}$ = e ∈ E, e belongs to some but not to all optimum solutions.},

author = {Vladimír Lacko},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {persistency; traveling salesman problem; Halin graph; polynomial algorithm; Halin graphs; persistency partition},

language = {eng},

number = {2},

pages = {231-242},

title = {Persistency in the Traveling Salesman Problem on Halin graphs},

url = {http://eudml.org/doc/270609},

volume = {20},

year = {2000},

}

TY - JOUR

AU - Vladimír Lacko

TI - Persistency in the Traveling Salesman Problem on Halin graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2000

VL - 20

IS - 2

SP - 231

EP - 242

AB - For the Traveling Salesman Problem (TSP) on Halin graphs with three types of cost functions: sum, bottleneck and balanced and with arbitrary real edge costs we compute in polynomial time the persistency partition $E_{All}$, $E_{Some}$, $E_{None}$ of the edge set E, where:
$E_{All}$ = e ∈ E, e belongs to all optimum solutions,
$E_{None}$ = e ∈ E, e does not belong to any optimum solution and
$E_{Some}$ = e ∈ E, e belongs to some but not to all optimum solutions.

LA - eng

KW - persistency; traveling salesman problem; Halin graph; polynomial algorithm; Halin graphs; persistency partition

UR - http://eudml.org/doc/270609

ER -

## References

top- [1] K. Cechlárová, Persistency in the assignment and transportation problems, Math. Methods of Operations Research 47 (1998) 234-254. Zbl0946.90099
- [2] K. Cechlárová and V. Lacko, Persistency in some combinatorial optimization problems, in: Proc. Mathematical Methods in Economy 99 (Jindrichúv Hradec, 1999) 53-60. Zbl0986.05026
- [3] K. Cechlárová and V. Lacko, Persistency in combinatorial optimization problems on matroids, to appear in Discrete Applied Math. Zbl0986.05026
- [4] G. Cornuéjols, D. Naddef and W.R. Pulleyblank, Halin graphs and the Traveling salesman problem, Mathematical Programming 26 (1983) 287-294, doi: 10.1007/BF02591867. Zbl0506.90083
- [5] M.C. Costa, Persistency in maximum cardinality bipartite matchings, Operations Research Letters 15 (1994) 143-149, doi: 10.1016/0167-6377(94)90049-3. Zbl0810.90126
- [6] V. Lacko, Persistency in optimization problems on graphs and matroids, Master Thesis, UPJS Košice, 1998. Zbl0986.05026
- [7] V. Lacko, Persistency in the matroid product problem, in: Proc. CEEPUS Modern Applied Math. Workshop (AGH Kraków, 1999), 47-51.

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.