An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width
- Title
- An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width
- Author
- 권오정
- Keywords
- Hamiltonian cycle; Eulerian trail; Clique-width; XP algorithm
- Issue Date
- 2020-06
- Publisher
- SPRINGER
- Citation
- ALGORITHMICA, v. 82, no. 6, page. 1654-1674
- Abstract
- 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://link.springer.com/article/10.1007/s00453-019-00663-9https://repository.hanyang.ac.kr/handle/20.500.11754/169022
- ISSN
- 0178-4617; 1432-0541
- DOI
- 10.1007/s00453-019-00663-9
- Appears in Collections:
- COLLEGE OF NATURAL SCIENCES[S](자연과학대학) > MATHEMATICS(수학과) > Articles
- Files in This Item:
There are no files associated with this item.
- Export
- RIS (EndNote)
- XLS (Excel)
- XML