University of Twente Student Theses
An implementable Three-in-a-tree algorithm to accelerate Perfect Graph detection
Hof, H.A. (2023) An implementable Three-in-a-tree algorithm to accelerate Perfect Graph detection.
This is the latest version of this item.
|
PDF
2MB |
| Abstract: | In this thesis we implement the algorithm of Chudnovsky et al.(2005) to determine if a given graph contains an odd-hole or anti-hole. In particular this decides whether a given graph is perfect according to the strong perfect graph theorem proved by Chudnovsky et al. (2006). A main bottleneck of this algorithm is the detection of pyramids in a given graph. We introduce the three-in-a-tree problem and develop new sub-algorithms to make the decision algorithm of Lai et al. (2020) self-standing and not based on other highly theoretical results. This new algorithm allows us to actually implement the three-in-a-tree algorithm and also leads to a reduced running time of detecting pyramids by three orders of magnitude. |
| Item Type: | Essay (Master) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 31 mathematics |
| Programme: | Applied Mathematics MSc (60348) |
| Link to this item: | https://purl.utwente.nl/essays/96789 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page