Parameterized computational complexity of finding small-diameter subgraphs

Schäfer, Alexander; Komusiewicz, Christian; Moser, Hannes; Niedermeier, Rolf

doi:10.1007/s11590-011-0311-5

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Journal Article

Parameterized computational complexity of finding small-diameter subgraphs

MPS-Authors

/persons/resource/persons19962

Schäfer, Alexander
Department Neurology, MPI for Human Cognitive and Brain Sciences, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Schäfer, A., Komusiewicz, C., Moser, H., & Niedermeier, R. (2012). Parameterized computational complexity of finding small-diameter subgraphs. Optimization Letters, 6(5), 883-891. doi:10.1007/s11590-011-0311-5.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0011-F31A-5

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.