BROWSE

Related Scientist

's photo.

수리및계산과학연구단
more info

ITEM VIEW & DOWNLOAD

A Polynomial Kernel for 3-Leaf Power Deletion

Cited 0 time in webofscience Cited 0 time in scopus
89 Viewed 0 Downloaded
Title
A Polynomial Kernel for 3-Leaf Power Deletion
Author(s)
Jungho Ahn; Eiben, Eduard; O. -Joung Kwon; Sang-Il Oum
Publication Date
2023-10
Journal
ALGORITHMICA, v.85, no.10, pp.3058 - 3087
Publisher
SPRINGER
Abstract
For a non-negative integer t, the t-leaf power of a tree T is a simple graph G on the leaves of T such that two vertices are adjacent in G if and only if their distance in T is at most t. We provide a polynomial kernel for the problem of deciding whether we can delete at most k vertices to make an input graph a 3-leaf power of some tree. More specifically, we present a polynomial-time algorithm for an input instance (G, k) for the problem to output an equivalent instance (G', k') such that k'= k and G' has at most O(k14) vertices.
URI
https://pr.ibs.re.kr/handle/8788114/14057
DOI
10.1007/s00453-023-01129-9
ISSN
0178-4617
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > 1. Journal Papers (저널논문)
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > 1. Journal Papers (저널논문)
Files in This Item:
There are no files associated with this item.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse