Maximum-size subgraphs of P4-sparse graphs admitting a perfect matching
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S. D.
Palios, L.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Advances in Informatics, Proceedings
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
In this paper, we address the problem of computing a maximum-size subgraph of a P-4-sparse graph which admits a perfect matching; in the case where the graph has a perfect matching, the solution to the problem is the entire graph. We establish a characterization of such subgraphs, and describe an algorithm for the problem which for a P-4-sparse graph on n vertices and m edges, runs in O(n + m) time and space. The above results also hold for the class of complement reducible graphs or cographs, a well-known subclass of P-4-sparse graphs.
Περιγραφή
Λέξεις-κλειδιά
perfect graphs, p-4-sparse graphs, cographs, maximum-size subgraphs, maximum matchings, perfect matching, recognition algorithm, p-4-sparse graphs, cographs
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής