7
Tôi gặp phải nhiều vấn đề có thể được xây dựng dưới dạng vấn đề đồ thị. Nó nói chung là NP-hard nhưng đôi khi đồ thị có thể được chứng minh là phẳng. Do đó, tôi quan tâm đến việc học những vấn đề này và các thuật toán.Danh sách các vấn đề chung về NP-hard nhưng có giải pháp đa thức trong đồ thị phẳng?
Cho đến nay như tôi biết:
- Max cắt trong đồ thị phẳng
- Bốn-tô màu trong đồ thị phẳng
- Max độc lập Set trong khối đồ thị phẳng
Hope một ai đó có thể hoàn thành danh sách này.
Tôi nghĩ rằng điều này thuộc về cstheory.se – Alexandru
Nhìn vào [FAQ] của họ [http://cstheory.stackexchange.com/faq), tôi nghĩ cstheory.se có thể sẽ đóng này. –
Tôi đã đóng cửa vì nó có vẻ như một câu hỏi "Danh sách X", nhưng tôi đang mở cửa lại với hy vọng rằng có một tài nguyên với câu trả lời. Nếu những người khác cảm thấy không có câu trả lời đúng, họ có thể bỏ phiếu để đóng. –