article

Halin graphs and the travelling salesman problem

Authors:

G. Cornuéjols,

D. Naddef,

W. R. PulleyblankAuthors Info & Claims

Mathematical Programming: Series A and B, Volume 26, Issue 3

Pages 287 - 294

https://doi.org/10.1007/BF02591867

Published: 01 October 1983 Publication History

Abstract

A Halin graphH=TźC is obtained by embedding a treeT having no nodes of degree 2 in the plane, and then adding a cycleC to join the leaves ofT in such a way that the resulting graph is planar. These graphs are edge minimal 3-connected, hamiltonian, and in general have large numbers of hamilton cycles. We show that for arbitrary real edge costs the travelling salesman problem can be polynomially solved for such a graph, and we give an explicit linear description of the travelling salesman polytope (the convex hull of the incidence vectors of the hamilton cycles) for such a graph.

References

[1]

G. Cornuéjols, D. Naddef and W.R. Pulleyblank, "The travelling salesman problem in graphs with 3-edge cutsets", Discussion paper no. 8212, Centre for Operations Research and Econometrics (Louvain-la-Neuve 1982).

Google Scholar

[2]

J. Edmonds and E.L. Johnson "Matching: a well-solved class of integer programs", in R.K. Guy et al., eds., Combinatorial structures and their applications (Gordon and Breach, New York, 1970) pp. 89-92.

Google Scholar

[3]

M. Grötschel, Polyedrische Charakterisierungen kombinatorischer Optimierungsprobleme (Verlag Anton Hain, Meisenheim am Glan, 1977).

Google Scholar

[4]

R. Halin, "Studies on minimally n-connected graphs", in D.J.A. Welsh, ed., Combinatorial mathematics, and its applications (Academic Press, New York 1971) pp. 129-136.

Google Scholar

[5]

L. Lovász and M. Plummer, "On a family of planar bicritical graphs", Proceedings of the London Mathematical Society 30 (1975) 160-176.

Crossref

Google Scholar

[6]

D. Naddef and W.R. Pulleyblank, "Ear decompositions of elementary graphs and GF2-rank of perfect matchings", Annals of Discrete Mathematics 16 (1982) 241-260.

Google Scholar

[7]

W.R. Pulleyblank, "The matching rank of Halin graphs", RR210, 1MAG, Université Scientifique et Médicale de Grenoble, France (1980).

Google Scholar

[8]

M. Syslo and A. Proskurowski, "On Halin graphs", to appear inProceedings of the Tagow Conference dedicated to the memory of R. Kuratowski (1981).

Google Scholar

Cited By

View all

Bekos MDa Lozzo GGriesbach SGronemann MMontecchiani FRaftopoulou C(2024)Book embeddings of k-framed graphs and k-map graphsDiscrete Mathematics10.1016/j.disc.2023.113690347:1Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1016/j.disc.2023.113690
Bekos MDa Lozzo GFrati FGronemann MMchedlidze TRaftopoulou C(2023)Recognizing DAGs with page-number 2 is NP-completeTheoretical Computer Science10.1016/j.tcs.2023.113689946:COnline publication date: 10-Feb-2023
https://dl.acm.org/doi/10.1016/j.tcs.2023.113689
He SLiu H(2023)The maximum number of short paths in a Halin graphDiscrete Optimization10.1016/j.disopt.2023.10080950:COnline publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1016/j.disopt.2023.100809
Show More Cited By

Halin graphs and the travelling salesman problem

Recommendations

The oriented chromatic number of Halin graphs

The oriented chromatic number of an oriented graph G is the minimum order of an oriented graph H such that G admits a homomorphism to H. The oriented chromatic number of an unoriented graph G is the maximal chromatic number over all possible ...
Edge-Face List Coloring of Halin Graphs
Algorithmic Aspects in Information and Management
Abstract
A plane graph G is k-edge-face colorable if the elements of can be colored with k colors such that any two adjacent or incident elements receive different colors. G is edge-face L-list colorable if for a given list assignment , there exists a ...
Extremal Halin graphs with respect to the signless Laplacian spectra

A Halin graph G is a plane graph constructed as follows: Let T be a tree on at least 4 vertices. All vertices of T are either of degree 1, called leaves, or of degree at least 3. Let C be a cycle connecting the leaves of T in such a way that C forms the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematical Programming: Series A and B

Mathematical Programming: Series A and B Volume 26, Issue 3

October 1983

119 pages

ISSN:0025-5610

Issue’s Table of Contents

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 October 1983

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bekos MDa Lozzo GGriesbach SGronemann MMontecchiani FRaftopoulou C(2024)Book embeddings of k-framed graphs and k-map graphsDiscrete Mathematics10.1016/j.disc.2023.113690347:1Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1016/j.disc.2023.113690
Bekos MDa Lozzo GFrati FGronemann MMchedlidze TRaftopoulou C(2023)Recognizing DAGs with page-number 2 is NP-completeTheoretical Computer Science10.1016/j.tcs.2023.113689946:COnline publication date: 10-Feb-2023
https://dl.acm.org/doi/10.1016/j.tcs.2023.113689
He SLiu H(2023)The maximum number of short paths in a Halin graphDiscrete Optimization10.1016/j.disopt.2023.10080950:COnline publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1016/j.disopt.2023.100809
Angelini PBekos MKindermann PMchedlidze T(2022)On mixed linear layouts of series-parallel graphsTheoretical Computer Science10.1016/j.tcs.2022.09.019936:C(129-138)Online publication date: 10-Nov-2022
https://dl.acm.org/doi/10.1016/j.tcs.2022.09.019
Brimkov BGeneson JJensen ABroussard JNowbandegani P(2022)Intersections and circuits in sets of line segmentsJournal of Combinatorial Optimization10.1007/s10878-021-00731-344:4(2302-2323)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1007/s10878-021-00731-3
Basu AConforti MDi Summa MJiang H(2022)Complexity of branch-and-bound and cutting planes in mixed-integer optimizationMathematical Programming: Series A and B10.1007/s10107-022-01789-5198:1(787-810)Online publication date: 7-Mar-2022
https://dl.acm.org/doi/10.1007/s10107-022-01789-5
Haddadan ANewman A(2022)Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of toursMathematical Programming: Series A and B10.1007/s10107-022-01784-w198:1(595-620)Online publication date: 21-Mar-2022
https://dl.acm.org/doi/10.1007/s10107-022-01784-w
Bekos MKaufmann MZielke C(2022)The Book Embedding Problem from a SAT-Solving PerspectiveGraph Drawing and Network Visualization10.1007/978-3-319-27261-0_11(125-138)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/978-3-319-27261-0_11
Bekos MFelsner SKindermann PKobourov SKratochvíl JRutter I(2022)The Rique-Number of GraphsGraph Drawing and Network Visualization10.1007/978-3-031-22203-0_27(371-386)Online publication date: 13-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-22203-0_27
Bekos MDa Lozzo GFrati FGronemann MMchedlidze TRaftopoulou C(2022)Recognizing DAGs with Page-Number 2 Is NP-completeGraph Drawing and Network Visualization10.1007/978-3-031-22203-0_26(361-370)Online publication date: 13-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-22203-0_26
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Recommendations

The oriented chromatic number of Halin graphs

Edge-Face List Coloring of Halin Graphs

Extremal Halin graphs with respect to the signless Laplacian spectra

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations