An Optimal XP Algorithm for Hamiltonian Cycle on Graphs of Bounded Clique-Width

Cited 0 time in webofscience Cited 0 time in scopus
41 Viewed 9 Downloaded
Title
An Optimal XP Algorithm for Hamiltonian Cycle on Graphs of Bounded Clique-Width
Author(s)
Bergougnoux B.; Kante M.M.; O-joung Kwon
Publication Date
2020-06
Journal
ALGORITHMICA, v.82, no., pp.1654 - 1674
Publisher
SPRINGER
Abstract
© 2019, Springer Science+Business Media, LLC, part of Springer Nature.In this paper, we prove that, given a clique-width k-expression of an n-vertex graph, Hamiltonian Cycle can be solved in time nO ( k ). This improves the naive algorithm that runs in time nO(k2) by Espelage et al. (Graph-theoretic concepts in computer science, vol 2204. Springer, Berlin, 2001), and it also matches with the lower bound result by Fomin et al. that, unless the Exponential Time Hypothesis fails, there is no algorithm running in time no ( k ) (Fomin et al. in SIAM J Comput 43:1541–1563, 2014). We present a technique of representative sets using two-edge colored multigraphs on k vertices. The essential idea is that, for a two-edge colored multigraph, the existence of an Eulerian trail that uses edges with different colors alternately can be determined by two information: the number of colored edges incident with each vertex, and the connectedness of the multigraph. With this idea, we avoid the bottleneck of the naive algorithm, which stores all the possible multigraphs on k vertices with at most n edges
URI
https://pr.ibs.re.kr/handle/8788114/7121
ISSN
0178-4617
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > Journal Papers (저널논문)
Files in This Item:
An Optimal XP Algorithm for Hamiltonian Cycle on Graphs of Bounded Clique-Width.pdfDownload

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse