1. Repository of OAI
  2. ΑΠΟΘΕΤΗΡΙΟ "ΟΛΥΜΠΙΑΣ"
  3. Σχολή Θετικών Επιστημών
  4. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
  5. Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)
Ελληνικά   English  
Please use this identifier to cite or link to this item: https://olympias.lib.uoi.gr/jspui/handle/123456789/10858
Full metadata record
DC FieldValueLanguage
dc.contributor.authorNikolopoulos, S. D.en
dc.contributor.authorPalios, L.en
dc.date.accessioned2015-11-24T17:01:02Z-
dc.date.available2015-11-24T17:01:02Z-
dc.identifier.issn0302-9743-
dc.identifier.urihttps://olympias.lib.uoi.gr/jspui/handle/123456789/10858-
dc.rightsDefault Licence-
dc.subjectperfect graphsen
dc.subjectp-4-sparse graphsen
dc.subjectcographsen
dc.subjectmaximum-size subgraphsen
dc.subjectmaximum matchingsen
dc.subjectperfect matchingen
dc.subjectrecognition algorithmen
dc.subjectp-4-sparse graphsen
dc.subjectcographsen
dc.titleMaximum-size subgraphs of P4-sparse graphs admitting a perfect matchingen
heal.typejournalArticle-
heal.type.enJournal articleen
heal.type.elΆρθρο Περιοδικούel
heal.languageen-
heal.accesscampus-
heal.recordProviderΠανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικήςel
heal.publicationDate2005-
heal.abstractIn 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.en
heal.journalNameAdvances in Informatics, Proceedingsen
heal.journalTypepeer reviewed-
heal.fullTextAvailabilityTRUE-
Appears in Collections:Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)

Show simple item record
Files in This Item:
File Description SizeFormat 
nikolopoulos-2005-Maximum-size subgraphs of P4-sparse graphs admitting a perfect matching.pdf202.48 kBAdobe PDFView/Open    Request a copy
Show simple item record  


This item is licensed under a Creative Commons License Creative Commons