Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/26671Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Lappas, E. | en |
| dc.contributor.author | Nikolopoulos, S. | en |
| dc.contributor.author | Palios, L. | en |
| dc.date.accessioned | 2015-12-11T13:32:42Z | - |
| dc.date.available | 2015-12-11T13:32:42Z | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/26671 | - |
| dc.rights | Default License | - |
| dc.subject | Permutation graphs, | en |
| dc.subject | Paired-domination | en |
| dc.subject | Domination | en |
| dc.subject | Algorithms | en |
| dc.subject | Complexity. | en |
| dc.title | An O(n)-time algorithm for the paired-domination problem on permutation graphs | en |
| heal.type | bookChapter | - |
| heal.type.en | Book chapter | en |
| heal.type.el | Κεφάλαιο βιβλίου | el |
| heal.generalDescription | 368-379 σ. | el |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής | el |
| heal.publicationDate | 2009 | - |
| heal.bibliographicCitation | Βιβλιογραφία: σ. 378-379 | el |
| heal.abstract | A vertex subset D of a graph G is a dominating set if every vertex of G is either in D or is adjacent to a vertex in D. The paired- domination problem on G asks for a minimum-cardinality dominating set S of G such that the subgraph induced by S contains a perfect matching; motivation for this problem comes from the interest in finding a small number of locations to place pairs of mutually visible guards so that the entire set of guards monitors a given area. The paired-domination problem on general graphs is known to be NP-complete. In this paper, we consider the paired-domination problem on permutation graphs. We define an embedding of permutation graphs in the plane which enables us to obtain an equivalent version of the problem involving points in the plane, and we describe a sweeping algorithm for this problem; if the permutation over the set N„ = {1,2,... ,n} defining a permutation graph G on n vertices is given, our algorithm computes a paired-dominating set of G in 0(n) time, and is therefore optimal. | en |
| heal.publisher | Springer Berlin / Heidelberg | en |
| heal.fullTextAvailability | true | - |
| heal.bookName | - | en |
| Appears in Collections: | Μονογραφίες ( Κλειστές) | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs.pdf | 353.16 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
