Original title:
CSP nad orientovanými stromy
Translated title:
CSP over oriented trees
Authors:
Tatarko, William ; Bulín, Jakub (advisor) ; Barto, Libor (referee) Document type: Bachelor's theses
Year:
2019
Language:
eng Abstract:
[eng][cze] In this thesis we present an oriented tree with only 26 vertices, whose CSP is NP-complete. This serves as a counterexample for a conjecture that any oriented tree with this property has at least 39 vertices. The work itself is divided into three chapters. In the first one, basic definitions and tools of this topic are introduced. Then, tractability of trees of special shapes is shown. Finally, NP-completeness of a certain oriented tree is proven. 1V této práci představíme orientovaný strom, který má pouze 26 vrcholů a jehož CSP je NP-úplné. Toto slouží jako protipříklad k domněnce, že každý orientovaný strom s touto vlastností má alespoň 39 vrcholů. Práce je rozdělena do tří kapitol. V první představíme základní definice a poznatky tohoto tématu. Následně ukážeme, že orientované stromy určitých tvarů mají CSP řešitelné v polynomiálním čase. Nakonec dokážeme, že CSP jistého orientovaného stromu je NP-úplné. 1
Keywords:
CSP; NP-completeness; oriented trees; CSP; NP-úplnost; orientované stromy
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/108042