|
|||||
|
|
Parameterized computational complexity of finding small-diameter subgraphs |
|
| Authors: | Alexander Schäfer Christian Komusiewicz Hannes Moser Rolf Niedermeier |
| Institution: | 1.Department of Neurology,Max Planck Institute for Human Cognitive and Brain Sciences,Leipzig,Germany;2.Institut für Softwaretechnik und Theoretische Informatik,Technische Universtit?t Berlin,Berlin,Germany;3.Institut für Informatik,Friedrich-Schiller-Universit?t Jena,Jena,Germany |
| Abstract: | Finding subgraphs of small diameter in undirected graphs has been seemingly unexplored from a parameterized complexity perspective. We perform the first parameterized complexity study on the corresponding NP-hard s-Club problem. We consider two parameters: the solution size and its dual. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |