Efficient algorithms for the hamiltonian problem on distance-hereditary graphs

Sun Yuan Hsieh, Chin Wen Ho, Tsan Sheng Hsu, Ming Tat Ko

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

8 Scopus citations

Abstract

In this paper, we first present an O(|V | + |E|)-time sequential algorithm to solve the Hamiltonian problem on a distance-hereditary graph G = (V,E). This algorithm is faster than the previous best result which takes O(|V|2) time. Let Td(|V|, |E|) and Pd(|V|, |E|) denote the parallel time and processor complexities, respectively, required to construct a decomposition tree of a distance-hereditary graph on a PRAM model Md.We also show that this problem can be solved in O(Td(|V|,|E|) + log |V|) time using O(Pd(|V|, |E|) + (|V | + |E|)/ log |V |) processors on Md. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in O(log |V |) time using O((|V | + |E|)/ log |V |) processors on an EREW PRAM.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 8th Annual International Conference, COCOON 2002, Proceedings
EditorsOscar H. Ibarra, Louxin Zhang
PublisherSpringer Verlag
Pages77-86
Number of pages10
ISBN (Print)354043996X, 9783540439967
DOIs
StatePublished - 2002
Event8th Annual International Conference on Computing and Combinatorics, COCOON 2002 - Singapore, Singapore
Duration: 15 Aug 200217 Aug 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2387
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference8th Annual International Conference on Computing and Combinatorics, COCOON 2002
Country/TerritorySingapore
CitySingapore
Period15/08/0217/08/02

Fingerprint

Dive into the research topics of 'Efficient algorithms for the hamiltonian problem on distance-hereditary graphs'. Together they form a unique fingerprint.

Cite this