Recognition algorithm for vertex-minors = Vertex-minor를 찾는 알고리즘

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 11
  • Download : 0
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.
Advisors
Oum, Sang-ilresearcher엄상일researcher
Description
한국과학기술원 :수리과학과,
Publisher
한국과학기술원
Issue Date
2019
Identifier
325007
Language
eng
Description

학위논문(석사) - 한국과학기술원 : 수리과학과, 2019.2,[ii, 22 p. :]

Keywords

Vertex-minor▼arank-width▼alocal complementation

URI
http://hdl.handle.net/10203/266409
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=843279&flag=dissertation
Appears in Collection
MA-Theses_Master(석사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0