Reconfiguring Independent Sets in Claw-Free Graphs

P.S. Bonsma, Marcin Kamiński, Marcin Wrochna

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    43 Citations (Scopus)
    27 Downloads (Pure)

    Abstract

    We present a polynomial-time algorithm that, given two independent sets in a claw-free graph G, decides whether one can be transformed into the other by a sequence of elementary steps. Each elementary step is to remove a vertex v from the current independent set S and to add a new vertex w (not in S) such that the result is again an independent set. We also consider the more restricted model where v and w have to be adjacent.
    Original languageUndefined
    Title of host publicationProceedings of the 14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014
    EditorsR. Ravi, Inge Li Gørtz
    Place of PublicationSwitzerland
    PublisherSpringer
    Pages86-97
    Number of pages12
    ISBN (Print)978-3-319-08403-9
    DOIs
    Publication statusPublished - Jul 2014
    Event14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014 - Copenhagen , Denmark
    Duration: 2 Jul 20144 Jul 2014
    Conference number: 14
    http://algolog.compute.dtu.dk/swat2014/

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer International Publishing
    Volume8503
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014
    Abbreviated titleSWAT 2014
    CountryDenmark
    CityCopenhagen
    Period2/07/144/07/14
    Internet address

    Keywords

    • EWI-25463
    • Reconfiguration
    • Token Sliding
    • METIS-309751
    • IR-93932
    • Claw-free graph
    • Graph algorithms

    Cite this

    Bonsma, P. S., Kamiński, M., & Wrochna, M. (2014). Reconfiguring Independent Sets in Claw-Free Graphs. In R. Ravi, & I. L. Gørtz (Eds.), Proceedings of the 14th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2014 (pp. 86-97). (Lecture Notes in Computer Science; Vol. 8503). Switzerland: Springer. https://doi.org/10.1007/978-3-319-08404-6_8