Hamiltonian cycle is polynomial on cocomparability graphs

Jitender S. Deogun; George Steiner

doi:10.1016/0166-218X(92)90168-A

Hamiltonian cycle is polynomial on cocomparability graphs

Jitender S. Deogun, George Steiner

Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

Finding a Hamiltonian path or a Hamiltonian cycle in a general graph are classic NP-complete problems. In this paper we announce polynomial time solutions for these problems on cocomparability graphs. Our approach is based on exploiting the relationship between the Hamiltonian problem in a cocomparability graph G and the bump number problem in a partial order, the comparability graph of which is the complement of G.

Original language	English (US)
Pages (from-to)	165-172
Number of pages	8
Journal	Discrete Applied Mathematics
Volume	39
Issue number	2
DOIs	https://doi.org/10.1016/0166-218X(92)90168-A
State	Published - Oct 22 1992

Keywords

Hamiltonian cycle
Hamiltonian path
bump number
cocomparability graphs
partial order

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/0166-218X(92)90168-A

Cite this

@article{84edca3f7d9548858528423d6d2dab0d,

title = "Hamiltonian cycle is polynomial on cocomparability graphs",

abstract = "Finding a Hamiltonian path or a Hamiltonian cycle in a general graph are classic NP-complete problems. In this paper we announce polynomial time solutions for these problems on cocomparability graphs. Our approach is based on exploiting the relationship between the Hamiltonian problem in a cocomparability graph G and the bump number problem in a partial order, the comparability graph of which is the complement of G.",

keywords = "Hamiltonian cycle, Hamiltonian path, bump number, cocomparability graphs, partial order",

author = "Deogun, {Jitender S.} and George Steiner",

note = "Funding Information: da L8S 4Kl. *This research was supported in part by the Office of Naval Research under Grant No. NOOOl4-91-J-1693 for the first author and the Natural Sciences and Engineering Research Council of Canada under Grant No. Al798 for the second author.",

year = "1992",

month = oct,

day = "22",

doi = "10.1016/0166-218X(92)90168-A",

language = "English (US)",

volume = "39",

pages = "165--172",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Hamiltonian cycle is polynomial on cocomparability graphs

AU - Deogun, Jitender S.

AU - Steiner, George

N1 - Funding Information: da L8S 4Kl. *This research was supported in part by the Office of Naval Research under Grant No. NOOOl4-91-J-1693 for the first author and the Natural Sciences and Engineering Research Council of Canada under Grant No. Al798 for the second author.

PY - 1992/10/22

Y1 - 1992/10/22

N2 - Finding a Hamiltonian path or a Hamiltonian cycle in a general graph are classic NP-complete problems. In this paper we announce polynomial time solutions for these problems on cocomparability graphs. Our approach is based on exploiting the relationship between the Hamiltonian problem in a cocomparability graph G and the bump number problem in a partial order, the comparability graph of which is the complement of G.

AB - Finding a Hamiltonian path or a Hamiltonian cycle in a general graph are classic NP-complete problems. In this paper we announce polynomial time solutions for these problems on cocomparability graphs. Our approach is based on exploiting the relationship between the Hamiltonian problem in a cocomparability graph G and the bump number problem in a partial order, the comparability graph of which is the complement of G.

KW - Hamiltonian cycle

KW - Hamiltonian path

KW - bump number

KW - cocomparability graphs

KW - partial order

UR - http://www.scopus.com/inward/record.url?scp=38249010520&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38249010520&partnerID=8YFLogxK

U2 - 10.1016/0166-218X(92)90168-A

DO - 10.1016/0166-218X(92)90168-A

M3 - Article

AN - SCOPUS:38249010520

SN - 0166-218X

VL - 39

SP - 165

EP - 172

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 2

ER -

Hamiltonian cycle is polynomial on cocomparability graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this