DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Oum, Sang-il | - |
dc.contributor.advisor | 엄상일 | - |
dc.contributor.author | Jeong, Jisu | - |
dc.date.accessioned | 2019-08-25T02:40:41Z | - |
dc.date.available | 2019-08-25T02:40:41Z | - |
dc.date.issued | 2018 | - |
dc.identifier.uri | http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=734348&flag=dissertation | en_US |
dc.identifier.uri | http://hdl.handle.net/10203/264942 | - |
dc.description | 학위논문(박사) - 한국과학기술원 : 수리과학과, 2018.2,[iv, 130 p. :] | - |
dc.description.abstract | We study width parameters on graphs, hypergraphs, matroids, and linear codes, which are combinatorial structures. A width parameter on a combinatorial structure is a measure of how thick its tree-like structure or its path-like structure is. There are various width parameters depending on the definition of a tree-like structure or a path-like structure and its thickness. We define width parameters on vector spaces, which are called the branch-width and the path-width. For the branch-width of subspaces of a vector space, we use a branch-decomposition as a tree-like structure and use the dimension of vector spaces as the thickness. For the path-width of subspaces of a vector space, we use a linear layout as a path-like structure and use the dimension of vector spaces as the thickness. Many combinatorial problems are NP-hard. However, if an input is given with its thin tree-like structure or path-like structure, then the problem can solved in polynomial time. One of our main results is to provide a fixed-parameter algorithm, for input subspaces of a vector space and an integer k, that determines whether a branch-decomposition of width at most k exists, and if it exists, finds such a branch-decomposition. In addition, we provide a fixed-parameter algorithm, for input subspaces of a vector space and an integer k, that determines whether a linear layout of width at most k exists, and if it exists, finds such a linear layout. From the algorithms, we present an analogous fixed-parameter algorithm for each of the following width parameters: the rank-width and the linear rank-width of graphs, the branch-width and the linear-width of hypergraphs, the carving-width and the cut-width of graphs, the branch-width and the path-width of matroids represented over a fixed finite field, and the trellis-width of linear codes. | - |
dc.language | eng | - |
dc.publisher | 한국과학기술원 | - |
dc.subject | Parameterized algorithm▼afixed-parameter algorithm▼abranch-width▼apath-width▼arank-width▼alinear rank-width▼acarving-width▼acut-width▼alinear-width▼atrellis-width | - |
dc.title | Parameterized algorithms for width parameters | - |
dc.title.alternative | Width parameters에 대한 매개변수 알고리즘 | - |
dc.type | Thesis(Ph.D) | - |
dc.identifier.CNRN | 325007 | - |
dc.description.department | 한국과학기술원 :수리과학과, | - |
dc.contributor.alternativeauthor | 정지수 | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.