On structural parameterizations for the 2-club problem

DOI10.1016/j.dam.2014.11.026zbMath1311.05051arXiv1305.3735OpenAlexW2962860656MaRDI QIDQ2341718

Ondřej Suchý, André Nichterlein, Christian Komusiewicz, Sepp Hartung

Publication date: 28 April 2015

Published in: Discrete Applied Mathematics, Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

fixed-parameter tractabilitysocial network analysisclique relaxationsmultivariate complexity analysiscohesive subnetworksparameter hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (14)

Optimal approximation algorithms for maximum distance-bounded subgraph problems ⋮ On Fault-Tolerant Low-Diameter Clusters in Graphs ⋮ The parameterized complexity of \(s\)-club with triangle and seed constraints ⋮ On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering ⋮ Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule? ⋮ Finding clubs in graph classes ⋮ Computing dense and sparse subgraphs of weakly closed graphs ⋮ Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ On integer programming models for the maximum 2-club problem and its robust generalizations in sparse graphs ⋮ The parameterized complexity of \(s\)-club with triangle and seed constraints ⋮ Even better fixed-parameter algorithms for bicluster editing ⋮ Distance-Based Clique Relaxations in Networks: s-Clique and s-Club ⋮ Algorithms and complexity of \(s\)-club cluster vertex deletion

Cites Work

• Unnamed Item
• Fundamentals of parameterized complexity
• Finding clubs in graph classes
• On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs
• Finding large \(k\)-clubs in undirected graphs
• Upper bounds and heuristics for the 2-club problem
• On the parameterized complexity of multiple-interval graph problems
• On problems without polynomial kernels
• An exact algorithm for the maximum \(k\)-club problem in an undirected graph
• Parameterized computational complexity of finding small-diameter subgraphs
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Heuristics for finding \(k\)-clubs in an undirected graph
• Parametrized complexity theory.
• Tight lower bounds for certain parameterized NP-hard problems
• Novel approaches for analyzing biological networks
• On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal
• Kernel Bounds for Structural Parameterizations of Pathwidth
• New Races in Parameterized Algorithmics
• Emergence of Scaling in Random Networks
• Reflections on Multivariate Algorithmics and Problem Parameterization
• The h-Index of a Graph and its Application to Dynamic Subgraph Statistics
• Approximating Maximum Diameter-Bounded Subgraphs
• A graph‐theoretic definition of a sociometric clique†
• A graph‐theoretic generalization of the clique concept
• Graph Classes: A Survey
• Parameterized Algorithmics and Computational Experiments for Finding 2-Clubs
• Integer models and upper bounds for the 3‐club problem

This page was built for publication: On structural parameterizations for the 2-club problem