서지주요정보
Recognition algorithm for vertex-minors = Vertex-minor를 찾는 알고리즘
서명 / 저자 Recognition algorithm for vertex-minors = Vertex-minor를 찾는 알고리즘 / Yeong-joon Kang.
저자명 Kang, Yeong-joon ; 강영준
발행사항 [대전 : 한국과학기술원, 2019].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8033681

소장위치/청구기호

학술문화관(도서관)2층 패컬티라운지(학위논문)

MMAS 19001

SMS전송 소장위치

도서상태

이용가능

대출가능

반납예정일

초록정보

We show that for every fi xed graph H with $l V(H) l \leqslant 6$, one can decide whether the input graph contains a vertex-minor isomorphic to H in polynomial time. To show this, we prove that for every graph H with $l V(H) l \leqslant 6$, graphs having no vertex-minor isomorphic to H have bounded rank-width, unless H is locally equivalent to the wheel graph on 6 vertices.

이 논문에서는 꼭짓점 개수가 6개 이하인 정해진 그래프에 대해서, 입력된 그래프가 정해진 그래프를 vertex-minor로 가지는가에 대한 문제를 다항 시간 안에 풀 수 있음을 증명한다. 이를 증명하기 위해, 꼭짓점 개수가 6개 이하인 정해진 그래프가 꼭짓점이 6개인 휠 그래프와 locally equivalent 하지 않다면, 정해진 그래프를 vertex-minor로 가지지 않는 그래프의 rank-width는 상한을 가진다는 것을 증명한다.

서지기타정보

서지기타정보
청구기호 {MMAS 19001
형태사항 ii, 22 p. : 삽도 ; 30 cm
언어 영어
일반주기 저자명의 한글표기 : 강영준
지도교수의 영문표기 : Sang-il Oum
지도교수의 한글표기 : 엄상일
학위논문 학위논문(석사) - 한국과학기술원 : 수리과학과,
서지주기 References : p. 20-21
주제 Vertex-minor
rank-width
local complementation
Vertex-minor
rank-width
local complementation
QR CODE qr code