| Presentation | 2019-05-11 Parameterized Algorithms for Order Dimension Yasuaki Kobayashi, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The {em dimension} of a partially ordered set (poset) is known to be one of the fundamental complexity measures of posets. We consider the problem of computing the dimention of posets. It is known that the problem of deciding if the dimension of a given poset is at most $k$ is NP-complete for any fixed $k ge 3$. In this paper, we consider structural parameterizations of graphs obtained from a given poset and show the fixed-parameter tractability results with respect to well-known graph parameters. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | partially ordered set / dimension / fixed-parameter algorithm / treewidth |
| Paper # | COMP2019-8 |
| Date of Issue | 2019-05-03 (COMP) |
| Conference Information | |
| Committee | COMP / IPSJ-AL |
|---|---|
| Conference Date | 2019/5/10(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Kumamoto University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Toshihiro Fujito(Toyohashi Univ. of Tech.) / 瀧本 英二(九州大学) |
| Vice Chair | Shinichi Nakano(Gunma Univ.) |
| Secretary | Shinichi Nakano(Kyoto Univ.) / (Kumamoto Univ) |
| Assistant | Kazuhisa Seto(Seikei Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Parameterized Algorithms for Order Dimension |
| Sub Title (in English) | |
| Keyword(1) | partially ordered set |
| Keyword(2) | dimension |
| Keyword(3) | fixed-parameter algorithm |
| Keyword(4) | treewidth |
| 1st Author's Name | Yasuaki Kobayashi |
| 1st Author's Affiliation | Kyoto University(Kyoto Univ.) |
| Date | 2019-05-11 |
| Paper # | COMP2019-8 |
| Volume (vol) | vol.119 |
| Number (no) | COMP-21 |
| Page | pp.pp.91-95(COMP), |
| #Pages | 5 |
| Date of Issue | 2019-05-03 (COMP) |