Nhận biết chu trình dominating là NP-đầy đủ

Chỉ số đề mục

28.21

Lĩnh vực nghiên cứu

Khoa học máy tính và thông tin

Dạng tài liệu

Tác giả

Vũ Đình Hoà, NGUYỄN DUY KHANH⁽¹⁾

Nhan đề

Nhận biết chu trình dominating là NP-đầy đủ

Nhan đề tiếng anh

Nguồn trích

TC Tin học và điều khiển học

Năm xuất bản

2002

Số

3

Trang

226-230

ISSN

Từ khóa

Chu trình dominating cycle, Nhận dạng

Từ khóa tiếng anh

Tóm tắt

Vấn đề xác định xem sự tồn tại của chu trình Halmiton trong một đồ thị cho trước được biết là một vấn đề NP-đầy đủ, và do đó vấn đề này thường được xem xét trong các lớp đồ thị đặc biệt, chẳng hạn trong các đồ thị 1-tough, hoặc được chuyển sang xem xét các đồ thị dominating. Tác giả chỉ ra rằng vấn đề xác định xem một đồ thị cho trước có chu trình dominating hay không cũng vẫn còn là bài toán NP-đầy đủ

Tóm tắt tiếng anh

Kí hiệu kho

TTTTKHCNQG, CVv 127

File toàn văn

Xem toàn văn