Graph Square Roots of Small Distance from Degree One Graphs
- Petr Golovach,
- ,
- Charis Papadopoulos
- University of Bergen,
- ,
- University of Ioannina
Research Output:
Journal Article or Conference Article in Journal
Journal article
Peer-reviewOpen access
Publication Information
Output type
Research Output:
Journal Article or Conference Article in Journal
Journal article
Peer-reviewOriginal language
EnglishPages from-to (Number of pages)
Pages 821-846Journal (Volume, Issue Number)
Theory of Computing Systems (Volume 66)Publication milestones
- Published - 2022
Publication status
Published - 2022
ISSN
1432-4350Publication IDs
- Scopus: 85129179545
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
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
Publication metrics
PlumX, opens in new tab
Captures
1
Access to documents
Accepted author manuscript
Final published version
