Luận án này trình bày các thuật toán chính xác nhanh hơn (về mặt thời gian chạy trong trường hợp xấu nhất) cho các trường hợp đặc biệt của bài toán đồ thị thông qua quy hoạch động và lập trình 2-SAT. Lập trình động mô tả quy trình chia nhỏ một bài toán một cách đệ quy thành các bài toán con chồng chéo, tức là các bài toán con có các bài toán con chung. Đưa ra giải pháp tối ưu cho các bài toán con này, chương trình động sau đó kết hợp chúng thành giải pháp tối ưu cho bài toán ban đầu. Lập trình 2-SAT đề cập đến quy trình rút gọn một bài toán thành một tập hợp các công thức 2-SAT, tức là các công thức boolean ở dạng chuẩn liên hợp trong đó mỗi mệnh đề chứa tối đa hai chữ. Việc tính toán xem một công thức như vậy có thỏa mãn hay không (và tính toán một phép gán chân lý thỏa mãn, nếu có) sẽ mất thời gian tuyến tính theo độ dài của công thức. Do đó, khi thỏa mãn phép gán chân trị cho một số công thức 2-SAT tương ứng với lời giải của bài toán ban đầu và tất cả các công thức đều có thể được tính toán một cách hiệu quả, tức là trong thời gian đa thức với kích thước đầu vào của bài toán ban đầu thì bài toán ban đầu có thể được giải. trong thời gian đa thức.

Abstract:

This thesis presents faster (in terms of worst-case running times) exact algorithms for special cases of graph problems through dynamic programming and 2-SAT programming. Dynamic programming describes the procedure of breaking down a problem recursively into overlapping subproblems, that is, subproblems with common subsubproblems. Given optimal solutions to these subproblems, the dynamic program then combines them into an optimal solution for the original problem. 2-SAT programming refers to the procedure of reducing a problem to a set of 2-SAT formulas, that is, boolean formulas in conjunctive normal form in which each clause contains at most two literals. Computing whether such a formula is satisfiable (and computing a satisfying truth assignment, if one exists) takes linear time in the formula length. Hence, when satisfying truth assignments to some 2-SAT formulas correspond to a solution of the original problem and all formulas can be computed efficiently, that is, in polynomial time in the input size of the original problem, then the original problem can be solved in polynomial time.

Ngôn ngữ:	En
Tác giả:	Bentert, Matthias
Thông tin nhan đề:	Elements of dynamic and 2-SAT programming: paths, trees, and cuts
Nhà xuất bản:	Universitätsverlag der Technischen Universität Berlin
Loại hình:	Tài nguyên giáo dục mở / Bộ sưu tập: Công nghệ thông tin
Bản quyền:	https://creativecommons.org/licenses/by/4.0/
Nguồn gốc:	https://directory.doabooks.org/handle/20.500.12854/81574
Mô tả vật lý:	213p.
Năm xuất bản:	2021