Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/10930Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Asdre, K. | en |
| dc.contributor.author | Nikolopoulos, S. D. | en |
| dc.date.accessioned | 2015-11-24T17:01:28Z | - |
| dc.date.available | 2015-11-24T17:01:28Z | - |
| dc.identifier.issn | 0028-3045 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/10930 | - |
| dc.rights | Default Licence | - |
| dc.subject | perfect graphs | en |
| dc.subject | complement reducible graphs | en |
| dc.subject | cographs | en |
| dc.subject | cotree | en |
| dc.subject | path cover | en |
| dc.subject | fixed-endpoint path cover | en |
| dc.subject | linear-time algorithms | en |
| dc.subject | distance-hereditary graphs | en |
| dc.subject | circular-arc graphs | en |
| dc.subject | hamiltonian problems | en |
| dc.subject | interval-graphs | en |
| dc.title | A linear-time algorithm for the k-fixed-endpoint path cover problem on cographs | en |
| heal.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.identifier.primary | Doi 10.1002/Net.20200 | - |
| heal.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.publicationDate | 2007 | - |
| heal.abstract | In this paper, we study a variant of the path cover problem, namely, the k-fixed-endpoint path cover problem. Given a graph G and a subset T of k vertices of V(G), a k-fixed-endpoint path cover of G with respect to T is a set of vertex-disjoint paths P that covers the vertices of G such that the k vertices of T are all endpoints of the paths in P. The k-fixed-endpoint path cover problem is to find a k-fixed-endpoint path cover of G of minimum cardinality; note that, if T is empty, that is, k = 0, the stated problem coincides with the classical path cover problem. We show that the k-fixed-endpoint path cover problem can be solved in linear time on the class of cographs. More precisely, we first establish a lower bound on the size of a minimum k-fixed-endpoint path cover of a cograph and prove structural properties for the paths of such a path cover. Then, based on these properties, we describe an algorithm which, for a cograph G on n vertices and m edges, computes a minimum k-fixed-endpoint path cover of G in linear time, that is, in O(n + m) time. The proposed algorithm is simple, requires linear space, and also enables us to solve some path cover related problems, such as the 1 HIP and 2HP, on cographs within the same time and space complexity. (c) 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(4), 231-240 2007 | en |
| heal.journalName | Networks | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά) | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Asdre-2007-A linear-time algori.pdf | 207.96 kB | Adobe PDF | View/Open Request a copy |
This item is licensed under a Creative Commons License
