Please use this identifier to cite or link to this item: https://olympias.lib.uoi.gr/jspui/handle/123456789/11033
Full metadata record
DC FieldValueLanguage
dc.contributor.authorAsdre, K.en
dc.contributor.authorNikolopoulos, S. D.en
dc.date.accessioned2015-11-24T17:02:16Z-
dc.date.available2015-11-24T17:02:16Z-
dc.identifier.issn0304-3975-
dc.identifier.urihttps://olympias.lib.uoi.gr/jspui/handle/123456789/11033-
dc.rightsDefault Licence-
dc.subjectperfect graphsen
dc.subjectproper interval graphsen
dc.subjectpath coveren
dc.subjectfixed-endpoint path coveren
dc.subjectlinear-time algorithmsen
dc.subjectfinding hamiltonian circuitsen
dc.subjectlinear-time recognitionen
dc.subjectdisjoint pathsen
dc.subjectalgorithmen
dc.subjectcographsen
dc.titleA polynomial solution to the k-fixed-endpoint path cover problem on proper interval graphsen
heal.typejournalArticle-
heal.type.enJournal articleen
heal.type.elΆρθρο Περιοδικούel
heal.identifier.primaryDOI 10.1016/j.tcs.2009.11.003-
heal.languageen-
heal.accesscampus-
heal.recordProviderΠανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικήςel
heal.publicationDate2010-
heal.abstractWe study a variant of the path cover problem, namely, the k-fixed-endpoint path cover problem, or kPC for short. 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 kPC problem is to find a k-fixed-endpoint path cover of G of minimum cardinality; note that, if T is empty (or, equivalently, k = 0), the stated problem coincides with the classical path cover problem. The kPC problem generalizes some path cover related problems, such as the 1HP and 2HP problems, which have been proved to be NP-complete. Note that the complexity status for both 1HP and 2HP problems on interval graphs remains an open question (Damaschke ( 1993)[9]). In this paper, we show that the kPC problem can be solved in linear time on the class of proper interval graphs, that is, in O(n + m) time on a proper interval graph on n vertices and m edges. The proposed algorithm is simple, requires linear space. and also enables us to solve the 1HP and 2HP problems on proper interval graphs within the same time and space complexity. (C) 2009 Elsevier B.V. All rights reserved.en
heal.journalNameTheoretical Computer Scienceen
heal.journalTypepeer reviewed-
heal.fullTextAvailabilityTRUE-
Appears in Collections:Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)

Files in This Item:
File Description SizeFormat 
Asdre-2010-A polynomial solutio.pdf1.05 MBAdobe PDFView/Open    Request a copy


This item is licensed under a Creative Commons License Creative Commons