Graph Square Roots of Small Distance from Degree One Graphs

Petr Golovach, Paloma Thomé de Lima, Charis Papadopoulos

Publikation: Artikel i tidsskrift og konference artikel i tidsskriftTidsskriftartikelForskningpeer review

Abstract

Given a graph class H, the task of the H-Square Root problem is to decide whether
an input graph G has a square root H from H. We are interested in the parameterized
complexity of the problem for classes H that are composed by the graphs at vertex deletion
distance at most k from graphs of maximum degree at most one, that is, we are looking
for a square root H such that there is a modulator S of size k such that H − S is the
disjoint union of isolated vertices and disjoint edges
OriginalsprogEngelsk
TidsskriftTheory of Computing Systems
Vol/bind66
Sider (fra-til)821-846
ISSN1432-4350
DOI
StatusUdgivet - 2022

Emneord

  • Vertex cover
  • Structural parameterization
  • Square root

Fingeraftryk

Dyk ned i forskningsemnerne om 'Graph Square Roots of Small Distance from Degree One Graphs'. Sammen danner de et unikt fingeraftryk.

Citationsformater