Name
Abstract | ||
|---|---|---|
A generalized split (k,l) partition is a vertex set partition into at most k independent sets and l cliques. We prove that the (2, 1) partitioned probe problem is in P whereas the (2, 2) partitioned probe is NP-complete. The full complexity dichotomy into polynomial time and NP-complete for the class of generalized split partitioned probe problems establishes (2, 2) as the first NP-complete self-complementary partitioned probe problem, and answers negatively the PGC conjecture by finding a polynomial time recognition problem whose partitioned probe version is NP-complete. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.endm.2013.10.007 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
Probe graphs,partition problems,graph sandwich problems,graph algorithms,computational complexity | Partition problem,Discrete mathematics,Graph algorithms,Combinatorics,Vertex (geometry),Partition of a set,Time complexity,Partition (number theory),Conjecture,Mathematics,Computational complexity theory | Journal |
Volume | ISSN | Citations |
44 | 1571-0653 | 1 |
PageRank | References | Authors |
0.37 | 15 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Simone Dantas | 1 | 119 | 24.99 |
| Luerbio Faria | 2 | 133 | 20.98 |
| Celina M. Herrera de Figueiredo | 3 | 9 | 2.67 |
| Rafael B. Teixeira | 4 | 49 | 5.31 |