✦ LIBER ✦

The node-deletion problem for hereditary properties is NP-complete

✍ Scribed by John M. Lewis; Mihalis Yannakakis

Publisher: Elsevier Science
Year: 1980
Tongue: English
Weight: 801 KB
Volume: 20
Category: Article
ISSN: 0022-0000
DOI: 10.1016/0022-0000(80)90060-4

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The Hamiltonian circuit problem for circ

The Hamiltonian circuit problem for circle graphs is NP-complete

✍ Peter Damaschke 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 134 KB

The edge Hamiltonian path problem is NP-

The edge Hamiltonian path problem is NP-complete for bipartite graphs

✍ Ten-Hwang Lai; Shu-Shang Wei 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 508 KB

Approximating Element-Weighted Vertex De

Approximating Element-Weighted Vertex Deletion Problems for the Complete k-Partite Property

✍ Reuven Bar-Yehuda; Dror Rawitz 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 143 KB

A k-partite graph is a graph G s V , . . . , V , E , where V , . . . , V are k non- We discuss three variants of the following optimization i / j i j problem: given a graph and a non-negative weight function on the vertices and edges, find a minimum weight set of vertices and incident edges whose r