Duc A. Hoang 0001

dblp:147/5383 · DBLP profile ↗
← Back
9ranked-venue papers
4as first author
3since 2021 · last 2026
0000-0002-8635-8462ORCID · verified

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 9 · 4 first-author · 3 since 2021
YearPublicationVenuePosition
2026 Distance Recoloring
Niranka Banerjee, Christian Engels, Duc A. Hoang 0001
COCOON3
2024 The Complexity of Distance-r Dominating Set Reconfiguration
Niranka Banerjee, Duc A. Hoang 0001
COCOON (1)2
2024 On the complexity of distance-d independent set reconfiguration
Duc A. Hoang 0001
Theor. Comput. Sci.1
2020 Reconfiguring k-path Vertex Covers
Duc A. Hoang 0001, Akira Suzuki 0001, Tsuyoshi Yagita
WALCOM1
2019 Shortest Reconfiguration Sequence for Sliding Tokens on Spiders
Duc A. Hoang 0001, Amanj Khorramian, Ryuhei Uehara
CIAC1
2016 Sliding Tokens on a Cactus
abstract
Given two independent sets I and J of a graph G, imagine that a token (coin) is placed on each vertex in I. Then, the Sliding Token problem asks if one could transforms I to J using a sequence of elementary steps, where each step requires sliding a token from one vertex to one of its neighbors, such that the resulting set of vertices where tokens are placed still remains independent. In this paper, we describe a polynomial-time algorithm for solving Sliding Token in case the graph G is a cactus. Our algorithm is designed based on two observations. First, all structures that forbid the existence of a sequence of token slidings between I and J, if exist, can be found in polynomial time. A no-instance may be easily deduced using this characterization. Second, without such forbidden structures, a sequence of token slidings between I and J does exist.
Duc A. Hoang 0001, Ryuhei Uehara
ISAAC1
2015 Sliding Token on Bipartite Permutation Graphs
Eli Fox-Epstein, Duc A. Hoang 0001, Yota Otachi, Ryuhei Uehara
ISAAC2
2015 Linear-time algorithm for sliding tokens on trees
Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang 0001, Takehiro Ito, Hirotaka Ono 0001, Yota Otachi, Ryuhei Uehara, Takeshi Yamada
Theor. Comput. Sci.4
2014 Polynomial-Time Algorithm for Sliding Tokens on Trees
Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang 0001, Takehiro Ito, Hirotaka Ono 0001, Yota Otachi, Ryuhei Uehara, Takeshi Yamada
ISAAC4