On the complexity of graph reconstruction期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

On the complexity of graph reconstruction

Authors:

Affiliation:

1.Fakult?t für Mathematik und Informatik, Friedrich-Schiller-Universit?t, 07740, Jena, Germany
;2.Department of Computer Science, University of Rochester, 14627, Rochester, NY, USA
;

Abstract:

In the wake of the resolution of the four-color conjecture, the graph reconstruction conjecture has emerged as one focal point of graph theory. This paper considers thecomputational complexity of decision problems (Deck Checking andLegitimate Deck), construction problems (Preimage Construction), and counting problems (Preimage Counting) related to the graph reconstruction conjecture. We show that:

${\text{GRAPH}} {\text{ISOMORPHISM}} \leqslant _m^l LEGITIMATE DECK, and$

Keywords:
本文献已被 SpringerLink 等数据库收录！

设为首页 | 免责声明 | 关于勤云 | 加入收藏