| ชื่อเรื่อง | : | On NP-hardness of the clique partition : independence number gap recognition and related problems. |
| นักวิจัย | : | Busygin, Stanislav. , Pasechnik, Dmitrii V. |
| คำค้น | : | DRNTU::Science::Mathematics::Discrete mathematics::Theory of computation. |
| หน่วยงาน | : | Nanyang Technological University, Singapore |
| ผู้ร่วมงาน | : | - |
| ปีพิมพ์ | : | 2549 |
| อ้างอิง | : | Busygina, S., & Pasechnikb, D. V. (2006). On NP-hardness of the clique partition: independence number gap recognition and related problems. Discrete Mathematics, 306(4), 460–463. , http://hdl.handle.net/10220/8272 , http://dx.doi.org/10.1016/j.disc.2006.01.004 |
| ที่มา | : | - |
| ความเชี่ยวชาญ | : | - |
| ความสัมพันธ์ | : | Discrete mathematics |
| ขอบเขตของเนื้อหา | : | - |
| บทคัดย่อ/คำอธิบาย | : | We show that for a graph G it is NP-hard to decide whether its independence number α(G) equals its clique partition number ¯χ(G) even when some minimum clique partition of G is given. This implies that any α(G)-upper bound provably better than ¯χ (G) is NP-hard to compute. To establish this result we use a reduction of the quasigroup completion problem (QCP, known to be NP-complete) to the maximum independent set problem. A QCP instance is satisfiable if and only if the independence number α(G) of the graph obtained within the reduction is equal to the number of holes h in the QCP instance. At the same time, the inequality ¯χ (G)≤ h always holds. Thus, QCP is satisfiable if and only if α(G) = ¯χ (G) = h. Computing the Lovász number ϑ(G) we can detect QCP unsatisfiability at least when ¯χ (G) |
| บรรณานุกรม | : |
Busygin, Stanislav. , Pasechnik, Dmitrii V. . (2549). On NP-hardness of the clique partition : independence number gap recognition and related problems..
กรุงเทพมหานคร : Nanyang Technological University, Singapore. Busygin, Stanislav. , Pasechnik, Dmitrii V. . 2549. "On NP-hardness of the clique partition : independence number gap recognition and related problems.".
กรุงเทพมหานคร : Nanyang Technological University, Singapore. Busygin, Stanislav. , Pasechnik, Dmitrii V. . "On NP-hardness of the clique partition : independence number gap recognition and related problems.."
กรุงเทพมหานคร : Nanyang Technological University, Singapore, 2549. Print. Busygin, Stanislav. , Pasechnik, Dmitrii V. . On NP-hardness of the clique partition : independence number gap recognition and related problems.. กรุงเทพมหานคร : Nanyang Technological University, Singapore; 2549.
|
ridm@nrct.go.th ระบบคลังข้อมูลงานวิจัยไทย รายการโปรดที่คุณเลือกไว้
