Parameterized computational complexity of finding small-diameter subgraphs
From MaRDI portal
Publication:1758028
DOI10.1007/s11590-011-0311-5zbMath1254.90279OpenAlexW2051438793MaRDI QIDQ1758028
Christian Komusiewicz, Hannes Moser, Alexander Schaefer
Publication date: 7 November 2012
Published in: Optimization Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11590-011-0311-5
NP-hard problemclique relaxationproblem kernelpolynomial-time preprocessing\(s\)-clubbranching algorithm
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)
Related Items (31)
Finding a maximum \(k\)-club using the \(k\)-clique formulation and canonical hypercube cuts ⋮ Optimal approximation algorithms for maximum distance-bounded subgraph problems ⋮ Identifying risk-averse low-diameter clusters in graphs with stochastic vertex weights ⋮ Finding disjoint dense clubs in a social network ⋮ On Fault-Tolerant Low-Diameter Clusters in Graphs ⋮ Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems ⋮ The parameterized complexity of \(s\)-club with triangle and seed constraints ⋮ On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering ⋮ Algorithms for the maximum \(k\)-club problem in graphs ⋮ Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule? ⋮ Finding clubs in graph classes ⋮ On the tractability of finding disjoint clubs in a network ⋮ Computing dense and sparse subgraphs of weakly closed graphs ⋮ On the 2-Club Polytope of Graphs ⋮ On 2-clubs in graph-based data clustering: theory and algorithm engineering ⋮ Covering a Graph with Clubs ⋮ Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments ⋮ Finding Disjoint Dense Clubs in an Undirected Graph ⋮ Finding large \(k\)-clubs in undirected graphs ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ The parameterized complexity of \(s\)-club with triangle and seed constraints ⋮ Turing kernelization for finding long paths in graph classes excluding a topological minor ⋮ Hardness and tractability of the \(\gamma\)\textsf{-Complete Subgraph} problem ⋮ Turing kernelization for finding long paths and cycles in restricted graph classes ⋮ On the tractability of covering a graph with 2-clubs ⋮ Distance-Based Clique Relaxations in Networks: s-Clique and s-Club ⋮ On some FPT problems without polynomial Turing compressions ⋮ Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor ⋮ On structural parameterizations for the 2-club problem ⋮ An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems ⋮ Algorithms and complexity of \(s\)-club cluster vertex deletion
Cites Work
- Unnamed Item
- Infeasibility of instance compression and succinct PCPs for NP
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Finding the longest isometric cycle in a graph
- On problems without polynomial kernels
- On approximating the maximum diameter ratio of graphs
- An exact algorithm for the maximum \(k\)-club problem in an undirected graph
- Heuristics for finding \(k\)-clubs in an undirected graph
- Novel approaches for analyzing biological networks
- Approximating Maximum Diameter-Bounded Subgraphs
- A graph‐theoretic generalization of the clique concept
- Coalitions and payoffs in three‐person sequential games: Initial tests of two formal models
- Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
This page was built for publication: Parameterized computational complexity of finding small-diameter subgraphs
