Name
Abstract | ||
|---|---|---|
We study the complexity of editing a graph into a target graph with any fixed critical-clique graph. The problem came up in practice, in mining a huge word similarity graph for well structured word clusters. It also adds to the rich field of graph modification problems. We show in a generic way that several variants of this problem are in SUBEPT. As a special case, we give a tight time bound for edge deletion to obtain a single clique and isolated vertices, and we round up this study with NP-completeness results for a number of target graphs. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-319-04657-0_24 | ALGORITHMS AND COMPUTATION, WALCOM 2014 |
Keywords | Field | DocType |
np completeness | Discrete mathematics,Block graph,Combinatorics,Line graph,Clique graph,Graph property,Computer science,Simplex graph,Null graph,Symmetric graph,Split graph | Conference |
Volume | ISSN | Citations |
8344 | 0302-9743 | 1 |
PageRank | References | Authors |
0.42 | 10 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Damaschke | 1 | 471 | 56.99 |
| Olof Mogren | 2 | 60 | 4.41 |