Unit:
Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και ΥπολογισμούLibrary of the School of Science
Supervisors info:
Άρης Παγουρτζής Αναπλ. Καθηγητής (Επιβλέπων), Στάθης Ζάχος Καθηγητής, Δημήτρης Φωτάκης Επίκ. Καθηγητής
Original Title:
Counting complexity: compressed Ηamming distance, vertex covers and recent highlights
Translated title:
Μετρητική πολυπλοκότητα: συμπιεσμένη απόσταση Hamming, καλύμματα κορυφών και πρόσφατα επιτεύγματα
Summary:
In this article, we tackle the compressed Hamming distance problem. The Hamming
distance is an easy problem, but when we move to a compressed input (via the
SLP compression method) the problem becomes #P-complete. We propose a range of
algorithms for specific cases of the problem. Secondly, we deal with the
counting vertex covers problems in paths,cycles and trees, and answer more
specific questions like the probability of a vertex being part of a cover, and
the number of covers for any specific size some milestones of the field of the last 30 years.
Keywords:
Compressed Hamming Distance, Straight Line programs, Vertex covers, Counting, Algorithms
