Persistency in the Traveling Salesman Problem on Halin graphs
Vladimír Lacko
Discussiones Mathematicae Graph Theory, Tome 20 (2000), p. 231-242 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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 EAll, ESome, ENone of the edge set E, where: EAll = e ∈ E, e belongs to all optimum solutions, ENone = e ∈ E, e does not belong to any optimum solution and ESome = e ∈ E, e belongs to some but not to all optimum solutions.

Publié le : 2000-01-01
EUDML-ID : urn:eudml:doc:270609 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1122,
     author = {Vladim\'\i r Lacko},
     title = {Persistency in the Traveling Salesman Problem on Halin graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {20},
     year = {2000},
     pages = {231-242},
     zbl = {0982.05064},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1122}
}

Vladimír Lacko. Persistency in the Traveling Salesman Problem on Halin graphs. Discussiones Mathematicae Graph Theory, Tome 20 (2000) pp. 231-242. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1122/

[000] [1] K. Cechlárová, Persistency in the assignment and transportation problems, Math. Methods of Operations Research 47 (1998) 234-254. | Zbl 0946.90099

[001] [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. | Zbl 0986.05026

[002] [3] K. Cechlárová and V. Lacko, Persistency in combinatorial optimization problems on matroids, to appear in Discrete Applied Math. | Zbl 0986.05026

[003] [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. | Zbl 0506.90083

[004] [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. | Zbl 0810.90126

[005] [6] V. Lacko, Persistency in optimization problems on graphs and matroids, Master Thesis, UPJS Košice, 1998. | Zbl 0986.05026

[006] [7] V. Lacko, Persistency in the matroid product problem, in: Proc. CEEPUS Modern Applied Math. Workshop (AGH Kraków, 1999), 47-51.