STRING GRAPHS .2. RECOGNIZING STRING GRAPHS IS NP-HARD
STRING GRAPHS .2. RECOGNIZING STRING GRAPHS IS NP-HARD
复制标题
DOI：
10.1016/0095-8956(91)90091-w
复制
发表时间：
1991-05-01
影响因子：
1.4
通讯作者：
KRATOCHVIL, J
中科院分区：
文献类型：
--
作者：
KRATOCHVIL, J
Sinden[131]将弦图与薄膜rc电路联系起来。这个概念最初是由格雷厄姆在提出描述这些图的问题时使用的。这里我们没有给出弦图的表征，但另一方面，本文的结果表明不存在多项式表征（假设p# NP）。注意，弦图形成了图的诱导小闭类，但不是小闭类[6,81]。众所周知，每个小闭类都是多项式可识别的[11,121]，但识别一个诱导小闭类（即不是小闭类）可能是np完全的，甚至是不可确定的[10]。然而，弦图似乎形成了第一个自然诱导的小闭类，认识到它是已知的NP-hard。在这方面，让我们注意到，在[S]中表明临界（相对于取引子）非字符串图的数目是无限的。
String graphs were delined by Sinden [131 in connection with thin film RC-circuits. The notion itself was first used by Graham [3] while posing the problem of characterizing these graphs. We do not give a characterization of string graphs here, but on the other hand, the result of this paper indicates that no polynomial characterization exists (provided P# NP). Note that string graphs form an induced minor closed class but not minor closed class of graphs [6, 81. It is known that every minor closed class is polynomially recognizable [11, 121, but that recognizing an induced minor closed class (that is not minor closed) may be NP-complete or even undecidable [lo]. However, string graphs appear to form the first natural induced minor closed class, recognizing that is known to be NP-hard. In this connection let us remark that it is shown in [S] that the number of critical (with respect to taking induced minors) nonstring graphs is infinite.