Unit:
Κατεύθυνση / ειδίκευση Θεωρητική Πληροφορική (ΘΕΩ)Library of the School of Science
Author:
Πετρόπουλος Άγγελος
Supervisors info:
Βασίλειος Ζησιμόπουλος Καθηγητής
Original Title:
Το πρόβλημα των ζωτικών σημείων σε γραφήματα
Translated title:
The problem of vital points in graphs
Summary:
The knowledge of the critical points of a system is essential, in order to take
measures
for its protection from intentional strikes (like terrorists attacks) or
natural disasters. These systems are usually modelled as graph theoretic
problems, like minimum spanning tree, maximum matching, p-median problem etc.
For example, a point of a network may fail (i.e destroyed edge/s of a graph) or
a facility may fail (i.e destroyed node/s) which may lead a client node to an
alternative more expensive solution. So in a graph is crucial to know in
advance which edges or nodes failure will lead to the most expensive solution,
in order to take measures (for example reinforced patrol). These kind of
problems for general k (number of edges or nodes) are usually NP-hard. As a
consequence for general and big k algorithms for this kind of problem are
mostly of theoretical interest. For practical purposes we need to study and
research approximation algorithms for realistic computational time
but with drawback some error (within a desirable bound) in the final solution.
This thesis studies and presents this kind of problems from the current
bibliography.
Keywords:
Vital edges/nodes, Critical points, Protection models, Exact algorithms, Approximation algorithms
File:
File access is restricted only to the intranet of UoA.
document.pdf
2 MB
File access is restricted only to the intranet of UoA.
