The dense \(k\)-subgraph problem
From MaRDI portal
Publication:5930156
DOI10.1007/s004530010050zbMath0969.68117OpenAlexW2036836182MaRDI QIDQ5930156
Guy Kortsarz, David Peleg, Uriel Feige
Publication date: 17 April 2001
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s004530010050
Related Items (only showing first 100 items - show all)
Complexity of finding dense subgraphs ⋮ Chromatic kernel and its applications ⋮ The maximum exposure problem ⋮ Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width ⋮ Sharp spectral bounds of several graph parameters using eigenvector norms ⋮ Hardness and approximation of traffic grooming ⋮ Approximation and hardness results for the max \(k\)-uncut problem ⋮ A review on algorithms for maximum clique problems ⋮ The Densest $k$-Subhypergraph Problem ⋮ Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ Sequential vector packing ⋮ Iterated tabu search for the maximum diversity problem ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ An efficient algorithm for solving pseudo clique enumeration problem ⋮ \(k\)-edge subgraph problems ⋮ Approximation of the Quadratic Knapsack Problem ⋮ Happy set problem on subclasses of co-comparability graphs ⋮ Algorithms for the Densest Subgraph with at Least k Vertices and with a Specified Subset ⋮ An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs ⋮ Complexity and approximability of the happy set problem ⋮ Finding connected \(k\)-subgraphs with high density ⋮ Inequalities for the number of walks in graphs ⋮ Finding dense subgraphs with maximum weighted triangle density ⋮ Partially ordered knapsack and applications to scheduling ⋮ Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem ⋮ Solving \(k\)-cluster problems to optimality with semidefinite programming ⋮ On the approximability of the minimum rainbow subgraph problem and other related problems ⋮ Tight complexity bounds for FPT subgraph problems parameterized by the clique-width ⋮ A two-phase tabu search based evolutionary algorithm for the maximum diversity problem ⋮ Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem ⋮ Finding Connected Dense $$k$$-Subgraphs ⋮ Approximation with a fixed number of solutions of some multiobjective maximization problems ⋮ Computing densest \(k\)-subgraph with structural parameters ⋮ Classical benchmarking of Gaussian boson sampling on the Titan supercomputer ⋮ Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation ⋮ Approximation and Hardness Results for the Max k-Uncut Problem ⋮ On size-constrained minimum \(s\mathrm{-}t\) cut problems and size-constrained dense subgraph problems ⋮ Parameterized complexity of finding small degree-constrained subgraphs ⋮ Improved approximation algorithms for directed Steiner forest ⋮ Approximation of the quadratic knapsack problem ⋮ The densest \(k\)-subgraph problem on clique graphs ⋮ A linear time approximation scheme for computing geometric maximum \(k\)-star ⋮ Pruning 2-connected graphs ⋮ An approximation algorithm for the generalized \(k\)-multicut problem ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ The \textsc{max quasi-independent set} problem ⋮ On the approximability of some degree-constrained subgraph problems ⋮ On linearization techniques for budget-constrained binary quadratic programming problems ⋮ Graph clustering ⋮ A dynamic edge covering and scheduling problem: complexity results and approximation algorithms ⋮ A note on the set union knapsack problem ⋮ Long Term Memory and the Densest K-Subgraph Problem ⋮ On the advantage of overlapping clusters for minimizing conductance ⋮ An Efficient Algorithm for Enumerating Pseudo Cliques ⋮ Hardness and Approximation of Traffic Grooming ⋮ Distributed discovery of large near-cliques ⋮ Approximating \(k\)-generalized connectivity via collapsing HSTs ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ On set expansion problems and the small set expansion conjecture ⋮ Finding densest \(k\)-connected subgraphs ⋮ Top-\(k\) overlapping densest subgraphs ⋮ Single-machine scheduling with supporting tasks ⋮ A ``maximum node clustering problem ⋮ A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs ⋮ Approximating minimum-power degree and connectivity problems ⋮ On minimum power connectivity problems ⋮ Min sum clustering with penalties ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ How to allocate review tasks for robust ranking ⋮ Graph classes and approximability of the happy set problem ⋮ Dense and sparse graph partition ⋮ The complexity of detecting fixed-density clusters ⋮ Top-\(k\) overlapping densest subgraphs: approximation algorithms and computational complexity ⋮ Degree-Constrained Subgraph Problems: Hardness and Approximation Results ⋮ Mining relevant information on the Web: a clique-based approach ⋮ Graphs without a partition into two proportionally dense subgraphs ⋮ Optimal matroid partitioning problems ⋮ Community detection in dense random networks ⋮ Threshold-based preprocessing for approximating the weighted dense \(k\)-subgraph problem ⋮ How bad is forming your own opinion? ⋮ The densest subgraph problem with a convex/concave size function ⋮ An approximation algorithm to the \(k\)-Steiner forest problem ⋮ A branch-and-bound approach for maximum quasi-cliques ⋮ On the complexity and approximability of repair position selection problem ⋮ Polynomial-Time Algorithms for Multiple-Arm Identification with Full-Bandit Feedback ⋮ Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees ⋮ An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph ⋮ On approximating four covering and packing problems ⋮ Unnamed Item ⋮ Combinatorial properties and further facets of maximum edge subgraph polytopes ⋮ Breaking thermaxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem ⋮ Proportionally dense subgraph of maximum size: complexity and approximation ⋮ On majorization of closed walk vectors of trees with given degree sequences ⋮ Computing the \(k\) densest subgraphs of a graph ⋮ Approximating the maximum quadratic assignment problem ⋮ Improved approximation algorithms for maximum graph partitioning problems ⋮ An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems ⋮ A hybrid metaheuristic method for the maximum diversity problem ⋮ The hospitals/residents problem with lower quotas ⋮ PTAS for densest \(k\)-subgraph in interval graphs
This page was built for publication: The dense \(k\)-subgraph problem
