7 citations · 11 across the 7 of their papers we have counts for
10 papers
On finding short reconfiguration sequences between independent sets
Akanksha Agrawal, Soumita Hait, Amer E. Mouawad
Assume we are given a graph , two independent sets and in of size , and a positive integer . The goal is to decide whether there exists a sequ…
Token sliding on graphs of girth five
Valentin Bartier, Nicolas Bousquet, Jihad Hanna +2
In the Token Sliding problem we are given a graph and two independent sets and in of size . The goal is to decide whether there exists a sequence $\la…
A survey on the parameterized complexity of the independent set and (connected) dominating set reconfiguration problems
Nicolas Bousquet, Amer E. Mouawad, Naomi Nishimura +1
A graph vertex-subset problem defines which subsets of the vertices of an input graph are feasible solutions. We view a feasible solution as a set of tokens placed on the vertices…
Parallel Vertex Cover Algorithms on GPUs
Peter Yamout, Karim Barada, Adnan Jaljuli +2
Finding small vertex covers in a graph has applications in numerous domains. Two common formulations of the problem include: Minimum Vertex Cover, which finds the smallest vertex c…
Galactic Token Sliding
Valentin Bartier, Nicolas Bousquet, Amer E. Mouawad
Given a graph and two independent sets and of size , the independent set reconfiguration problem asks whether there exists a sequence of -sized independent se…
On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets
Daniel Lokshtanov, Amer E. Mouawad, Fahad Panolan +1
In a reconfiguration version of an optimization problem the input is an instance of and two feasible solutions and . The objective is to determin…