Name
Title | ||
|---|---|---|
The Kernelization Complexity of Connected Domination in Graphs with (no) Small Cycles. |
Abstract | ||
|---|---|---|
In the problem the input consists of a graph and a positive integer , and the question is whether there is a set of at most vertices in —a of —such that (i) is a dominating set of , and (ii) the subgraph [] induced by is connected; the parameter is . The underlying decision problem is a basic connectivity problem which is long known to be NP-complete, and it has been extensively studied using several algorithmic approaches. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s00453-012-9681-z | Algorithmica |
Keywords | Field | DocType |
Connected dominating set,Kernelization,Girth,Fixed-parameter tractability,Kernel lower bounds | Kernelization,Discrete mathematics,Dominating set,Decision problem,Combinatorics,Parameterized complexity,Vertex (geometry),Connected component,Connected dominating set,Mathematics,Bidimensionality | Journal |
Volume | Issue | ISSN |
68 | 2 | 0178-4617 |
Citations | PageRank | References |
3 | 0.41 | 22 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Neeldhara Misra | 1 | 341 | 31.42 |
| Geevarghese Philip | 2 | 198 | 18.88 |
| Venkatesh Raman | 3 | 2268 | 153.49 |
| Saket Saurabh | 4 | 2023 | 179.50 |