首页    期刊浏览 2024年11月25日 星期一
登录注册

文章基本信息

  • 标题:Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems - a Survey
  • 作者:Tobias Riege ; Jörg Rothe
  • 期刊名称:Journal of Universal Computer Science
  • 印刷版ISSN:0948-6968
  • 出版年度:2006
  • 卷号:12
  • 期号:5
  • 页码:551-578
  • 出版社:Graz University of Technology and Know-Center
  • 摘要:This paper surveys some of the work that was inspired by Wagner's general technique to prove completeness in the levels of the boolean hierarchy over NP and some related results. In particular, we show that it is DP-complete to decide whether or not a given graph can be colored with exactly four colors, where DP is the second level of the boolean hierarchy. This result solves a question raised by Wagner in 1987, and its proof uses a clever reduction due to Guruswami and Khanna. Another result covered is due to Cai and Meyer: The graph minimal uncolorability problem is also DP-complete. Finally, similar results on various versions of the exact domatic number problem are discussed.
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有