서지주요정보
(A) polynomial kernel for 3-leaf power deletion = 3-leaf power 꼭짓점 제거 문제의 다항식 커널
서명 / 저자 (A) polynomial kernel for 3-leaf power deletion = 3-leaf power 꼭짓점 제거 문제의 다항식 커널 / Jungho Ahn.
발행사항 [대전 : 한국과학기술원, 2020].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8036139

소장위치/청구기호

학술문화관(문화관) 보존서고

MMAS 20004

휴대폰 전송

도서상태

이용가능

대출가능

반납예정일

리뷰정보

초록정보

A graph $G$ is an $\ell$-leaf power of a tree $T$ if $V(G)$ is equal to the set of leaves of $T$, and distinct vertices $v$ and $w$ of $G$ are adjacent if and only if the distance between $v$ and $w$ in $T$ is at most $\ell$. Given a graph $G$, 3-Leaf Power Deletion asks whether there is a set $S\subseteq V(G)$ of size at most $k$ such that $G\setminus S$ is a $3$-leaf power of some tree $T$. We provide a polynomial kernel for this problem. More specifically, we present a polynomial-time algorithm for an input instance $(G,k)$ to output an equivalent instance $(G',k')$ such that $k'\leq k$ and $G'$ has at most $O(k^{14}\log^{12}k)$ vertices.

주어진 트리 $T$의 $\ell$-leaf power란, $T$의 모든 리프들을 꼭짓점으로 가지고, $T$에서 거리가 $\ell$ 이하인 두 리프를 변으로 연결한 그래프를 말한다. 주어진 그래프 $G$에서 최대 $k$개의 꼭짓점을 제거해 어떤 트리의 $3$-leaf power가 되도록 하는 게 가능한지를 판별하는 문제를 3-Leaf Power Deletion이라고 한다. 그래프 $G$에서 그러한 최대 $k$개의 꼭짓점이 존재하면 $(G,k)$를 yes-instance라고 하자. 그리고 $(G,k)$가 yes-instance라는 조건과 $(G',k')$가 yes-instance라는 조건이 동치일 때, $(G,k)$와 $(G',k')$를 동치라고 하자. 우리는 주어진 $(G,k)$와 동치이며 최대 $O(k^{14}\log^{12}k)$개의 꼭짓점을 가지는 그래프 $G'$와 $k'\leq k$로 구성된 $(G',k')$을 다항식 시간 안에 생성하는 알고리즘을 제시했다.

서지기타정보

서지기타정보
청구기호 {MMAS 20004
형태사항 iii, 34 p. : 삽화 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 안정호
지도교수의 영문표기 : Sang-il Oum
지도교수의 한글표기 : 엄상일
학위논문 학위논문(석사) - 한국과학기술원 : 수리과학과,
서지주기 References : p. 28-30
QR CODE qr code