Εργαστήριο Τεχνολογίας Λογισμικού
0 votes
253 views

Καλησπέρα,

Στην 4η σειρά προτεινόμενων ασκήσεων, στην άσκηση 5, ζητείται να αποδειχθεί ότι το Min Leaf Spanning Tree (1) και το Steiner Tree (2) είναι NP complete προβλήματα.

Θα ήθελα να ρωτήσω ποια είναι η "διαίσθηση" για να επιλέξουμε για το (1) αναγωγή από το Hamilton Path ενώ για το (2) από το Vertex Cover, δεδομένου ότι τα 2 προβλήματα μοιάζουν αρκετά;

(Όσες αποδείξεις βρήκα online ακολουθούν τις ίδιες αναγωγές με τις λύσεις που δίνονται χωρίς να εξηγούν κάπως πώς κατέληξαν σε αυτές τις επιλογές).

Ευχαριστώ εκ των προτέρων!

in algorithms by (310 points) | 253 views

1 Answer

+1 vote
Best answer

Τα δύο πρόβλήματα (Min Leaf Spanning Tree και Steiner tree) είναι εντελώς διαφορετικά ως προς το φύση τους. Για το Min Leaf Spanning Tree, η επιλογή του Hamilton Path είναι προφανής, πιστεύω. Το Min Leaf Spanning Tree είναι γενίκευση του Hamilton Path (το Hamilton Path είναι ένα spanning tree με 2 μόλις φύλλα). Για το Steiner tree, η επιλογή του Vertex Cover δεν είναι προφανής και δεν υπάρχει άλλος ιδιαίτερος λόγος επιλογής από το γεγονός ότι απλά το reduction γίνεται σχετικά εύκολα.

by (2.5k points)
selected by

301 questions

289 answers

288 comments

903 users