On the tractability of finding disjoint clubs in a network

DOI10.1016/j.tcs.2019.03.045zbMath1423.68333OpenAlexW2931193898WikidataQ128092427 ScholiaQ128092427MaRDI QIDQ2422030

Riccardo Dondi, Italo Zoppis, Giancarlo Mauri

Publication date: 18 June 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.03.045

zbMATH Keywords

graph algorithmsfixed-parameter algorithmsAPX-hardnessgraph problems\(s\)-clubs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering ⋮ On 2-clubs in graph-based data clustering: theory and algorithm engineering ⋮ On integer programming models for the maximum 2-club problem and its robust generalizations in sparse graphs ⋮ On the tractability of covering a graph with 2-clubs

Cites Work

• Unnamed Item
• Unnamed Item
• Finding clubs in graph classes
• Finding large \(k\)-clubs in undirected graphs
• Partition into cliques for cubic graphs: Planar case, complexity and approximation
• Some APX-completeness results for cubic graphs
• An exact algorithm for the maximum \(k\)-club problem in an undirected graph
• Covering with clubs: complexity and approximability
• Multivariate algorithmics for finding cohesive subnetworks
• Parameterized computational complexity of finding small-diameter subgraphs
• An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
• Novel approaches for analyzing biological networks
• The Design of Approximation Algorithms
• A graph‐theoretic definition of a sociometric clique†
• Color-coding
• Finding Disjoint Dense Clubs in an Undirected Graph
• Reducibility among Combinatorial Problems
• Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs

This page was built for publication: On the tractability of finding disjoint clubs in a network