NP-completeness results for some problems on subclasses of bipartite and chordal graphs
| dc.contributor.author | Asdre, K. | en |
| dc.contributor.author | Nikolopoulos, S. D. | en |
| dc.date.accessioned | 2015-11-24T17:01:29Z | |
| dc.date.available | 2015-11-24T17:01:29Z | |
| dc.identifier.issn | 0304-3975 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/10931 | |
| dc.rights | Default Licence | - |
| dc.subject | harmonious coloring | en |
| dc.subject | pair-complete coloring | en |
| dc.subject | k-path partition | en |
| dc.subject | bipartite permutation graphs | en |
| dc.subject | convex graphs | en |
| dc.subject | quasi-threshold graphs | en |
| dc.subject | threshold graphs | en |
| dc.subject | np-completeness | en |
| dc.subject | achromatic number | en |
| dc.subject | threshold graphs | en |
| dc.subject | complexity | en |
| dc.subject | algorithms | en |
| dc.subject | trees | en |
| dc.title | NP-completeness results for some problems on subclasses of bipartite and chordal graphs | en |
| heal.abstract | Extending previous NP-completeness results for the harmonious coloring problem and the pair-complete coloring problem on trees, bipartite graphs and cographs, we prove that these problems are also NP-complete on connected bipartite permutation graphs. We also study the k-path partition problem and, motivated by a recent work of Steiner [G. Steiner, On the k-path partition of graphs, Theoret. Comput. Sci. 290 (2003) 2147-2155], where he left the problem open for the class of convex graphs, we prove that the k-path partition problem is NP-complete on convex graphs. Moreover, we study the complexity of these problems on two well-known subclasses of chordal graphs namely quasi-threshold and threshold graphs. Based on the work of Bodlaender [H.L. Bodlaender, Achromatic number is NP-complete for cographs and interval graphs, Inform. Process. Lett. 31 (1989) 135-138], we show NP-completeness results for the pair-complete coloring and harmonious coloring problems on quasi-threshold graphs. Concerning the k-path partition problem, we prove that it is also NP-complete on this class of graphs. It is known that both the harmonious coloring problem and the k-path partition problem are polynomially solvable on threshold graphs. We show that the pair-complete coloring problem is also polynomially solvable on threshold graphs by describing a linear-time algorithm. (c) 2007 Elsevier B.V. All rights reserved. | en |
| heal.access | campus | - |
| heal.fullTextAvailability | TRUE | - |
| heal.identifier.primary | DOI 10.1016/j.tcs.2007.05.012 | - |
| heal.journalName | Theoretical Computer Science | en |
| heal.journalType | peer reviewed | - |
| heal.language | en | - |
| heal.publicationDate | 2007 | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.type | journalArticle | - |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.type.en | Journal article | en |
Αρχεία
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.74 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: