Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

Reconfiguration in bounded bandwidth and tree-depth

Uproszczony widok
dc.abstract.enWe show that several reconfiguration problems known to be PSPACE-complete remain so even when limited to graphs of bounded bandwidth (and hence pathwidth and treewidth). The essential step is noticing the similarity to very limited string rewriting systems, whose ability to directly simulate Turing Machines is classically known. On the other hand, we show that a large class of natural reconfiguration problems (coming from graph homomorphisms) becomes tractable on graphs of bounded tree-depth, and prove a dichotomy showing this to be in some sense tight.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorWrochna, Marcin
dc.date.accessioned2024-01-25T18:57:57Z
dc.date.available2024-01-25T18:57:57Z
dc.date.issued2017
dc.description.financeNie dotyczy
dc.description.volume93
dc.identifier.doi10.1016/J.JCSS.2017.11.003
dc.identifier.issn0022-0000
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/118037
dc.identifier.weblinkhttps://www.sciencedirect.com/science/article/abs/pii/S0022000017302246?via%3Dihub
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofJournal of Computer and System Sciences
dc.relation.pages1-10
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.enReconfiguration
dc.subject.enRecoloring
dc.subject.enTreewidth
dc.subject.enBandwidth
dc.subject.enTree-depth
dc.subject.enGraph homomorphism
dc.titleReconfiguration in bounded bandwidth and tree-depth
dc.typeJournalArticle
dspace.entity.typePublication