An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
From MaRDI portal
Publication:2354725
DOI10.1016/j.dam.2015.04.029zbMath1317.05107OpenAlexW842423234MaRDI QIDQ2354725
Christian Komusiewicz, Manuel Sorge
Publication date: 24 July 2015
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2015.04.029
Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Density (toughness, etc.) (05C42)
Related Items (14)
Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems ⋮ Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem ⋮ On the tractability of finding disjoint clubs in a network ⋮ Computing dense and sparse subgraphs of weakly closed graphs ⋮ Unnamed Item ⋮ Covering a Graph with Clubs ⋮ Finding supported paths in heterogeneous networks ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ Exploiting c-Closure in Kernelization Algorithms for Graph Problems ⋮ The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs ⋮ Unnamed Item ⋮ Hardness and tractability of the \(\gamma\)\textsf{-Complete Subgraph} problem ⋮ Enumerating connected induced subgraphs: improved delay and experimental comparison ⋮ On the tractability of covering a graph with 2-clubs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Editing graphs into disjoint unions of dense clusters
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Algorithm engineering for color-coding with applications to signaling pathway detection
- Catalan numbers, their generalization, and their uses
- Which problems have strongly exponential complexity?
- Parameterized computational complexity of finding small-diameter subgraphs
- On the maximum quasi-clique problem
- Improved approximation bounds for the minimum rainbow subgraph problem
- Parameterized two-player Nash equilibrium
- Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
- Parameterized algorithms for graph partitioning problems
- Exact algorithms for problems related to the densest \(k\)-set problem
- Parametrized complexity theory.
- An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints
- The complexity of detecting fixed-density clusters
- Tight lower bounds for certain parameterized NP-hard problems
- Novel approaches for analyzing biological networks
- Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem
- The h-Index of a Graph and its Application to Dynamic Subgraph Statistics
- Kernel(s) for problems with no kernel
- A Remark on Stirling's Formula
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
- On Finding Dense Subgraphs
- Color-coding
- A Fast Parametric Maximum Flow Algorithm and Applications
- Finding Dense Subgraphs of Sparse Graphs
- Exact and Approximation Algorithms for Densest k-Subgraph
- Kernelization Lower Bounds by Cross-Composition
- Listing All Maximal Cliques in Large Sparse Real-World Graphs
- Network Analysis
- THE MAXIMUM CONNECTIVITY OF A GRAPH
- The dense \(k\)-subgraph problem
This page was built for publication: An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
