Recognizing HHDS-free graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Nikolopoulos, S. D.
Palios, L.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Graph-Theoretic Concepts in Computer Science
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
In this paper, we consider the recognition problem on the HHDS-free graphs, a class of homogeneously orderable graphs, and we show that it has polynomial time complexity. In particular, we describe a simple O(n(2) m)-time algorithm which determines whether a graph C on n vertices and m edges is HHDS-free. To the best of our knowledge, this is the first polynomial-time algorithm for recognizing this class of graphs.
Περιγραφή
Λέξεις-κλειδιά
hhd-free graphs, hhds-free graphs, sun, homogeneously orderable graphs, perfectly orderable graphs, recognition, perfectly orderable graphs
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής