Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | 권오정 | - |
dc.contributor.author | 이명환 | - |
dc.date.accessioned | 2023-09-27T02:09:54Z | - |
dc.date.available | 2023-09-27T02:09:54Z | - |
dc.date.issued | 2023. 8 | - |
dc.identifier.uri | http://hanyang.dcollection.net/common/orgView/200000685958 | en_US |
dc.identifier.uri | https://repository.hanyang.ac.kr/handle/20.500.11754/187249 | - |
dc.description.abstract | In this thesis, we introduce new graph width parameters, called α-edge-crossing width and edge-crossing width. These are defined in terms of the number of edges crossing a bag of a tree-cut decomposition. We compare them with other known graph parameters. We show that edge-crossing width is equivalent to the tree-partition-width. On the other hand, α-edge-crossing width is a new parameter; tree-cut width and α-edge-crossing width are incomparable, and they both lie between tree-partition-width and edge-cut width. We provide an approximation algorithm that for a given n-vertex graph G, and integers k and α, in time 2^O((α+k) log(α+k))n^2, either outputs a tree-cut decomposition certifying that the α- edge-crossing width of G is at most 2α^2 + 5k or reports the α-edge-crossing width of G is more than k. As applications, we show that for a fixed α, List Coloring and Precoloring Extension are fixed parameter tractable parameterized by α-edge-crossing width. It was known that they are fixed parameter tractable parameterized by edge-cut width. However, they were known to be W[1]-hard parameterized by tree-cut width. We close the complexity gap between these two parameters. | - |
dc.publisher | 한양대학교 | - |
dc.title | α-edge-crossing width and its applications | - |
dc.type | Theses | - |
dc.contributor.googleauthor | 이명환 | - |
dc.contributor.alternativeauthor | Myounghwan Lee | - |
dc.sector.campus | S | - |
dc.sector.daehak | 대학원 | - |
dc.sector.department | 수학과 | - |
dc.description.degree | Master | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.