التفاصيل البيبلوغرافية
| العنوان: |
THE COMPLEXITY OF THE LIST PARTITION PROBLEM FOR GRAPHS. |
| المؤلفون: |
Cameron, Kathie, Eschen, Elaine M., Hoàng, Chính T., Sritharan, R. |
| المصدر: |
SIAM Journal on Discrete Mathematics; 2007, Vol. 21 Issue 4, p900-929, 30p, 1 Diagram |
| مصطلحات موضوعية: |
COMPUTATIONAL mathematics, MATHEMATICAL research, COMPUTATIONAL complexity, PARTITIONS (Mathematics), ALGORITHMS |
| مستخلص: |
The κ-partition problem is as follows: Given a graph G and a positive integer κ, partition the vertices of G into at most κ parts A1, A2,...,Aκ, where it may be specified that Ai induces a stable set, a clique, or an arbitrary subgraph, and pairs Ai, Aj (i ≠ j) be completely nonadjacent, completely adjacent, or arbitrarily adjacent. The list κ-partition problem generalizes the κ-partition problem by specifying for each vertex x, a list L(x) of parts in which it is allowed to be placed. Many well-known graph problems can be formulated as list κ-partition problems: e.g., 3-colorability, clique cutset, stable cutset, homogeneous set, skew partition, and 2-clique cutset. We classify, with the exception of two polynomially equivalent problems, each list 4-partition problem as either solvable in polynomial time or NP-complete. In doing so, we provide polynomial-time algorithms for many problems whose polynomial-time solvability was open, including the list 2- clique cutset problem. This also allows us to classify each list generalized 2-clique cutset problem and list generalized skew partition problem as solvable in polynomial time or NP-complete. [ABSTRACT FROM AUTHOR] |
|
Copyright of SIAM Journal on Discrete Mathematics is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Complementary Index |
Full Text Finder