On the Complexity of Cover-Incomparability Graphs of Posets |
| |
| Authors: | Jana Maxová Pavla Pavlíková Daniel Turzík |
| |
| Affiliation: | (1) Department of Mathematics, Institute of Chemical Technology, Prague, Technická 5, 166 28 Praha 6, Czech Republic;(2) Institute for Theoretical Computer Science (ITI), Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic |
| |
| Abstract: | ![]()
In this paper we show that the recognition problem for C-I graphs of posets is NP-complete. On the other hand, we prove that induced subgraphs of C-I graphs are exactly complements of comparability graphs, and hence the recognition problem for induced subgraphs of C-I graphs of posets is polynomial. |
| |
| Keywords: | Poset Graph Transitive orientation NP-complete |
| 本文献已被 SpringerLink 等数据库收录！ |
|
