Journal
THEORETICAL COMPUTER SCIENCE
Volume 439, Issue -, Pages 9-15Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2012.03.004
Keywords
Reconfiguration; Independent set; Perfect graphs; Cographs; Even-hole-free graphs
Categories
Funding
- Agencija za raziskovalno dejavnost Republike Slovenije
- research program [P1-0285]
- research projects [J1-4010, J1-4021, N1-0011, BI-BE/11-12-F-004]
Ask authors/readers for more resources
We study problems of reconfigurability of independent sets in graphs. We consider three different models (token jumping, token sliding, and token addition and removal) and analyze relationships between them. We prove that independent set reconfigurability in perfect graphs (under any of the three models) generalizes the shortest path reconfigurability problem in general graphs and is therefore PSPACE-complete. On the positive side, we give polynomial results for even-hole-free graphs and P-4-free graphs. (C) 2012 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available