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 contribution

8 Citations (Scopus)

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
Publication statusPublished - 2002 Jan 1
Event8th Annual International Conference on Computing and Combinatorics, COCOON 2002 - Singapore, Singapore
Duration: 2002 Aug 152002 Aug 17

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

Other

Other8th Annual International Conference on Computing and Combinatorics, COCOON 2002
CountrySingapore
CitySingapore
Period02-08-1502-08-17

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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