Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/12828Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Papadopoulos, C. | en |
| dc.contributor.author | Nikolopoulos, S. D. | en |
| dc.contributor.author | Palios, L. | en |
| dc.date.accessioned | 2015-11-24T17:23:59Z | - |
| dc.date.available | 2015-11-24T17:23:59Z | - |
| dc.identifier.issn | 0304-3975 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/12828 | - |
| dc.rights | Default Licence | - |
| dc.subject | fully dynamic algorithm, P4-sparse graph, modular decomposition, recognition | en |
| dc.title | A Fully Dynamic Algorithm for the Recognition of P4-sparse Graphs | en |
| heal.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.publicationDate | 2012 | - |
| heal.abstract | In this paper, we solve the dynamic recognition problem for the class of P4- sparse graphs: the objective is to handle edge/vertex additions and deletions, to recognize if each such modification yields a P4-sparse graph, and if yes, to update a representation of the graph. Our approach relies on maintaining the modular decomposition tree of the graph, which we use for solving the recognition problem. We establish properties for each modification to yield a P4-sparse graph and obtain a fully dynamic recognition algorithm which handles edge modifications in O(1) time and vertex modifications in O(d) time for a vertex of degree d. Thus, our algorithm implies an optimal edges-only dynamic algorithm and a new optimal incremental algorithm for P4-sparse graphs. | en |
| heal.publisher | Elsevier | en |
| heal.journalName | Theoretical Computer Science | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά). ΜΑΘ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Papadopoulos-2012-a fully dynamic.pdf | 388.89 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
