Name
Abstract | ||
|---|---|---|
Various combinatorial problems on graphs can be approached by reducing the size of the graph according to certain rules. Given an instance of a graph problem, it is desirable to apply a sequence of self-reductions that is as long as possible so that the remaining graph is as small as possible. We show that computing maximum reduction sequences for two self-reduction operations — two-pair reduction and quasi-modular clique reduction — are NP-hard problems, and extend this result to larger sets of self-reductions. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1016/S0012-365X(00)00132-1 | Discrete Mathematics |
Keywords | Field | DocType |
maximum self-reduction sequence,self-reduction,complexity,graph colouring,np hard problem | Perfect graph,Block graph,Discrete mathematics,Combinatorics,Line graph,Clique graph,Graph property,Cograph,Butterfly graph,Mathematics,Split graph | Journal |
Volume | Issue | ISSN |
226 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jeffrey H. Kingston | 1 | 336 | 38.79 |
| Nicholas Paul Sheppard | 2 | 285 | 25.84 |