서지주요정보
Parameterized algorithms for width parameters = Width parameters에 대한 매개변수 알고리즘
서명 / 저자 Parameterized algorithms for width parameters = Width parameters에 대한 매개변수 알고리즘 / Jisu Jeong.
발행사항 [대전 : 한국과학기술원, 2018].
Online Access 원문보기 원문인쇄

등록번호

8032397

소장위치/청구기호

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

DMAS 18005

도서상태

이용가능(대출불가)

반납예정일

초록정보

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.

그래프와 하이퍼그래프, 매트로이드, 선형 코드 등의 조합 구조에서 width parameter를 연구했다. 조합 구조에서 width parameter는 그것의 트리 구조나 선형 구조가 얼마나 두꺼운지를 측정한 것이다. 트리 구조나 선형 구조, 그리고 그것의 두께를 정의하는 방법에 따라 다양한 width parameter들이 존재한다. 우리는 벡터 공간에서의 width parameter인 branch-width와 path-width를 정의했다. Branch-width를 정의할 때 트리 구조로 branch-decomposition을 사용하고 두께로 벡터 공간의 차원을 사용한다. 또한, path-width를 정의할 때는 선형 구조로 linear layout을 사용하고 두께로 벡터 공간의 차원을 사용한다. 많은 조합 문제들은 NP-hard이다. 그러나 만약 입력값과 함께 두께가 얇은 트리 구조나 선형 구조가 주어진다면 다항 시간에 풀 수 있다. 우리의 주요 결과는 벡터 공간의 부분공간들과 정수 k가 주어졌을 때, 너비가 k이하인 branch-decomposition이 존재하는지 판단하고, 존재한다면 그것을 출력하는 fixed-parameter 알고리즘과 너비가 k이하인 linear layout이 존재하는지 판단하고, 존재한다면 그것을 출력하는 fixed-parameter 알고리즘을 개발한 것이다. 이를 이용하여 그래프의 rank-width와 linear rank-width, 하이퍼그래프의 branch-width와 linear-width, 그래프의 carving-width와 cut-width, 매트로이드의 branch-width와 path-width, 선형 코드의 trellis-width 각각에 대해 비슷한 작업을 하는 fixed-parameter 알고리즘을 얻었다.

서지기타정보

청구기호 {DMAS 18005 iv, 130 p. : 삽화 ; 30 cm 영어 저자명의 한글표기 : 정지수 지도교수의 영문표기 : Sang-il Oum 지도교수의 한글표기 : 엄상일 수록잡지명 : "The "art of trellis decoding" is fixed-parameter tractable". IEEE Transactions on Information Theory, v.63. no.11, pp.7178-7205(2017) 학위논문(박사) - 한국과학기술원 : 수리과학과, Including references(p. 120-124) and index.
QR CODE

전체보기

전체보기