Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
- Peter Damaschke,
- Jitender S. Deogun,
- Dieter Kratsch,
- George Steiner
- … show all 4 hide
368
Downloads
200
Citations
9
Comments
Abstract
Hamiltonian Path/Cycle are well known NP-complete problems on general graphs, but their complexity status for permutation graphs has been an open question in algorithmic graph theory for many years. In this paper, we prove that theHamiltonian Path problem is solvable in polynomial time even for the larger class of cocomparability graphs. Our result is based on a nice relationship between Hamiltonian paths and the bump number of partial orders. As another consequence we get a new interpretation of the bump number in terms of path partitions, leading to polynomial time solutions of theHamiltonian Path/Cycle Completion problems in cocomparability graphs.
Communicated by R. H. Möhring
This research was supported in part by ONR for third author and by NSERC under grant number A1798 for fourth author.
Related Content
Supplementary Material (0)
References (16)
- A. A.Bertossi and M. A.Bonucelli (1986) Hamiltonian circuits in interval graph generalizations,Information Processing Letters 23, 195–200.
- A.Brandlstädt and D.Kratsch (1984) On the restriction of some NP-complete graph problems to permutation graphs, Report N/84/80, Friedrich-Schiller-Universität, Jena.
- D. G.Corneil, H.Lerchs, and L.Stewart Burlingham (1981) Complement reducible graphs,Discrete Applied Mathematics 3, 163–174.
- P. Damaschke (1992) Paths in interval graphs and circular arc graphs, forthcoming inDiscrete Math.
- P.Damaschke (1989) The Hamiltonian circuit problem for circle graphs is NP-complete,Information Processing Letters 32, 1–2.
- P. Damaschke and H. Müller (1992) Hamiltonian circuits in convex and chordal bipartite graphs, submitted toDiscrete Math.
- J. S. Deogun and G. Steiner (1990) Hamiltonian cycle is polynomial on cocomparability graphs, preprint.
- U.Faigle and R.Schrader (1986) A combinatorial bijection between linear extensions of equivalent orders,Discrete Mathematics 58, 295–301.
- M.Habib (1984) Comparability invariants,Annals of Discrete Mathematics 23, 371–386.
- M.Habib, R. H.Möhring, and G.Steiner (1988) Computing the bump number is easy,Order 5, 107–129.
- A.Itai, C. H.Papadimitriou, and J. L.Szwarcfiter (1982) Hamiltonian paths in grid graphs,SIAM Journal of Computing 11(4), 676–686.
- D. S.Johnson (1985) The NP-completeness column: an ongoing guide,Journal of Algorithms 6, 434–451.
- M.Keil (1985) Finding Hamiltonian Circuits in interval graphs,Information Processing Letters 20, 201–206.
- D. Kratsch and L. Stewart (1989) Domination on cocomparability graphs, preprint.
- C. S. J. A. Nash-Williams (1969) Hamiltonian circuits in graphs and digraphs, in G. Chartrand and S. F. Kapoor (eds),The Many Facets of Graph Theory, pp. 237–244, Berlin, Germany.
- A. A.Schäffer and B. B.Simons (1988) Computing the bump number with techniques from two-processor scheduling,Order 5, 131–141.
About this Article
- Title
- Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
- Journal
-
Order
Volume 8, Issue 4 , pp 383-391 - Cover Date
- 1991-12-01
- DOI
- 10.1007/BF00571188
- Print ISSN
- 0167-8094
- Online ISSN
- 1572-9273
- Publisher
- Kluwer Academic Publishers
- Additional Links
- Topics
- Keywords
-
- 05C45
- Hamiltonian paths and cycles
- partial orders
- bump number
- cocomparability graphs
- Authors
-
- Peter Damaschke (1) (2)
- Jitender S. Deogun (1) (2)
- Dieter Kratsch (1) (2)
- George Steiner (3)
- Author Affiliations
-
- 1. Department of Computer Science & Engineering, University of Nebraska-Lincoln, 68588-0115, Lincoln, NE, USA
- 2. Management Science and Information Systems Area, Faculty of Business, McMaster University, L8S 4M4, Hamilton, Ontario, Canada
- 3. Mathematische Fakultät, Friedrich-Schiller-Universität Jena, Universitätshochhaus. 17. OG, O 6900, Jena, Germany