The parameterized complexity of \(s\)-club with triangle and seed constraints

DOI10.1007/978-3-031-06678-8_23OpenAlexW4285202622MaRDI QIDQ2169965

Frank Sommer, Christian Komusiewicz, Jaroslav Garvardt

Publication date: 30 August 2022

Full work available at URL: https://arxiv.org/abs/2201.05654

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Fundamentals of parameterized complexity
• Finding clubs in graph classes
• Identifying large robust network clusters via new compact formulations of maximum \(k\)-club problems
• Finding large \(k\)-clubs in undirected graphs
• On problems without polynomial kernels
• An exact algorithm for the maximum \(k\)-club problem in an undirected graph
• On biconnected and fragile subgraphs of low diameter
• Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments
• Multivariate algorithmics for finding cohesive subnetworks
• Parameterized computational complexity of finding small-diameter subgraphs
• On clique relaxation models in network analysis
• The maximum \(l\)-triangle \(k\)-club problem: complexity, properties, and algorithms
• On structural parameterizations for the 2-club problem
• The triangle \(k\)-club problem
• Novel approaches for analyzing biological networks
• Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs
• Parameterized Algorithms