scientific article; zbMATH DE number 175833

MaRDI QIDQ4034894zbMATH OpenFDO

Authors L. I. Tyagunov

Publication date 18 May 1993

zbMATH Keywords

kernelNP-complete

Mathematics Subject Classification ID

Graph theory (05C99) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

[For the entire collection see Zbl 0746.00034.] It is proved that the following problems are NP-complete. \(\Pi_ 1\): An ordinary graph \(G=(V,E)\) and a non-empty set \(V'\subseteq V\) are given. Does kernel of the graph \(G\) exist in \(V'\)? \(\Pi_ 4\): A finite set \(S=\{a_ j:j\in\overline{1,n},n\geq 3\}\) and a family \(S_ 1,\dots,S_ m\) of its three-element subsets are given. Does a subset \(S'\subset S\) exist such that \(| S_ i-S'|=2\) for every \(i\in\overline{1,m}\)?

Recommendations

• Even kernels
• scientific article; zbMATH DE number 958366
• On the complexity of the 3-kernel problem in some classes of digraphs
• Overview of some solved NP-complete problems in graph theory
• NP-completeness of some problems of partitioning and covering in graphs

Cited in

(6)

• Even kernels
• Linearly-growing reductions of Karp's 21 NP-complete problems
• On the classification of NP-complete problems in terms of their correlation coefficient
• Overview of some solved NP-complete problems in graph theory
• scientific article; zbMATH DE number 5320331 (Why is no real title available?)
• scientific article; zbMATH DE number 958366 (Why is no real title available?)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4034894)