On choosing a dense subgraph

No abstract is available for this paper.

• Publication year

  1993

• Venue

  Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science

• Publication date

  1993-11-03

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/SFCS.1993.366818
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Generating Sparse 2-Spanners

  1992cited by this paper
• Facility Dispersion Problems: Heuristics and Special Cases (Extended Abstract)

  1991cited by this paper
• On the power of two-point based sampling

  1989cited by this paper
• A Fast Parametric Maximum Flow Algorithm and Applications

  1989cited by this paper
• Approximation algorithms for scheduling unrelated parallel machines

  1987cited by this paper
• A unified approach to approximation algorithms for bottleneck problems

  1986cited by this paper
• Probabilistic construction of deterministic algorithms: Approximating packing integer programs

  1986cited by this paper

• Efficient Algorithms for the Interval Maximum Coverage Problem

  2026cites this paper
• Supermodular Maximization with Cardinality Constraints

  2025influential citation
• Ensuring connectedness for the Maximum Quasi-clique and Densest k-subgraph problems

  2024cites this paper
• Diversity-Optimized Group Extraction in Social Networks

  2024cites this paper
• A Weighted Vertex Cover-Based Intensification Tabu Search for the Capacitated Dispersion Problem

  2024cites this paper
• Solving the Multiobjective Quasi-Clique Problem

  2024cites this paper
• The sparse sequences of graphs

  2024cites this paper
• Second-order moments of the size of randomly induced subgraphs of given order

  2023cites this paper
• A Survey on the Densest Subgraph Problem and its Variants

  2023cites this paper
• A New Conjecture on Hardness of 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems

  2023cites this paper
• Sum-of-Squares Lower Bounds for Densest k-Subgraph

  2023cites this paper
• Approximation Algorithm for Minimum p Union Under a Geometric Setting

  2022cites this paper
• Computing densest k-subgraph with structural parameters

  2022cites this paper
• An Ant Colony Optimisation Approach to the Densest k-Subgraph Problem*

  2022cites this paper
• Improved Parameterized Complexity of Happy Set Problems

  2022cites this paper
• How Hard Is Cyber-risk Management in IT/OT Systems? A Theory to Classify and Conquer Hardness of Insuring ICSs

  2022cites this paper
• Approximation Algorithms For The Dispersion Problems in a Metric Space

  2021cites this paper
• Complexity and approximability of the happy set problem

  2021cites this paper
• Conic Linear Programming

  2021cites this paper
• GRASP and tabu search for the generalized dispersion problem

  2021cites this paper
• Parameterized Algorithms for the Happy Set Problem

  2020cites this paper
• WALCOM: Algorithms and Computation: 14th International Conference, WALCOM 2020, Singapore, Singapore, March 31 – April 2, 2020, Proceedings

  2020cites this paper
• Hardness of Approximation of (Multi-)LCS over Small Alphabet

  2020cites this paper
• Approximating Max k-Uncut via LP-rounding Plus Greed, with Applications to Densest k-Subgraph

  2020cites this paper
• Graph Classes and Approximability of the Happy Set Problem

  2020cites this paper
• From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More

  2020cites this paper
• On solving the densest k-subgraph problem on large graphs

  2019cites this paper
• Beyond submodular maximization via one-sided smoothness

  2019cites this paper
• An Algorithm for Densest Subgraphs of Vertex-weighted Graphs

  2018cites this paper
• Finding Subsets Maximizing Minimum Structures

  2018cites this paper
• Voting on multi-issue domains with conditionally lexicographic preferences

  2018cites this paper
• . The Densest $k$-Subhypergraph Problem. SIAM Journal on Discrete Mathematics , 32 (2),

  2018cites this paper
• Improved approximation algorithm for the Dense-3-Subhypergraph Problem

  2017cites this paper
• From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More

  2017cites this paper
• Parameterized Approximation Algorithms for Bidirected Steiner Network Problems

  2017cites this paper
• Improved Approximation Algorithm for Steiner k-Forest with Nearly Uniform Weights

  2017cites this paper
• Less is more: Solving the Max-Mean diversity problem with variable neighborhood search

  2017cites this paper
• Effective metaheuristic algorithms for the minimum differential dispersion problem

  2017cites this paper
• Finding connected k-subgraphs with high density

  2017cites this paper
• Solving the maximum min-sum dispersion by alternating formulations of two different problems

  2017cites this paper
• Using a Conic Bundle Method to Accelerate Both Phases of a Quadratic Convex Reformulation

  2016cites this paper
• An optimal treatment assignment strategy to evaluate demand response effect

  2016cites this paper
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph

  2016cites this paper
• An iterated local search algorithm for the minimum differential dispersion problem

  2016cites this paper
• The Densest k-Subhypergraph Problem

  2016cites this paper
• A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs

  2016cites this paper
• Approximation algorithms for geometric dispersion

  2016cites this paper
• On size-constrained minimum s-t cut problems and size-constrained dense subgraph problems

  2016cites this paper
• Less is more: Basic variable neighborhood search for minimum differential dispersion problem

  2016cites this paper
• Optimization and Machine Learning Frameworks for Complex Network Analysis

  2016cites this paper
• On Parameterized Inapproximability of Several Optimization Problems

  2016cites this paper
• Theoretical Computer Science

  2015cites this paper
• CIDANE: comprehensive isoform discovery and abundance estimation

  2015cites this paper
• Algorithms for the Densest Subgraph with at Least k Vertices and with a Specified Subset

  2015cites this paper
• Finding Connected Dense k -Subgraphs

  2015influential citation
• Data Analysis through Polyhedral Theory From Land Consolidation to Circuit Diameters

  2015cites this paper
• Greedy randomized adaptive search procedure with exterior path relinking for differential dispersion minimization

  2015cites this paper
• Threshold-based preprocessing for approximating the weighted dense k-subgraph problem

  2014cites this paper
• An Efficient Lagrangian Smoothing Heuristic for the p-Dispersion-Sum Problem

  2014cites this paper
• GRASP WITH EXTERIOR PATH RELINKING FOR DIFFERENTIAL DISPERSION MINIMIZATION

  2014cites this paper
• PTAS for Densest $$k$$k-Subgraph in Interval Graphs

  2014cites this paper
• Edge covering problems with budget constrains

  2013cites this paper
• Graph Theoretic Clique Relaxations and Applications

  2013cites this paper
• Design and analysis of human identification protocols

  2012cites this paper
• A branch-and-bound approach for maximum quasi-cliques

  2012cites this paper
• Mining Statistically Significant Substrings using the Chi-Square Statistic

  2012cites this paper
• Everywhere-Sparse Spanners via Dense Subgraphs

  2012cites this paper
• Structural Properties of Rich Clubs

  2011cites this paper
• Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width

  2011cites this paper
• PTAS for Densest k-Subgraph in Interval Graphs

  2011cites this paper
• From Caesar to Twitter: An Axiomatic Approach to Elites of Social Networks

  2011cites this paper
• Approximating k-generalized connectivity via collapsing HSTs

  2011influential citation
• Integer point sets minimizing average pairwise L[subscript 1] distance: What is the optimal shape of a town?

  2010cites this paper
• Algorithms for Packing Problems

  2010cites this paper
• Densest k-Subgraph Approximation on Intersection Graphs

  2010cites this paper
• Integer Point Sets Minimizing Average Pairwise l1 Distance: What is the Optimal Shape of a Town?

  2010cites this paper
• Complexity Theory and Algorithms for Graph Problems Driven by Comparative Analysis of Large-Scale Biological Networks.

  2010cites this paper
• Weak Recovery Conditions from Graph Partitioning Bounds and Order Statistics

  2010influential citation
• Convex Relaxations for Subset Selection

  2010cites this paper
• Enumeration of isolated cliques and pseudo-cliques

  2009cites this paper
• On Finding Dense Subgraphs

  2009cites this paper
• Graph theoretic generalizations of clique: optimization and extensions

  2009cites this paper
• The equitable dispersion problem

  2009cites this paper
• Cluster Ensemble Selection

  2008cites this paper
• Short Cycles Make W-hard Problems Hard: FPT Algorithms for W-hard Problems in Graphs with no Short Cycles

  2008cites this paper
• A deterministic approximation algorithm for the Densest k-Subgraph Problem

  2008cites this paper
• An Introduction to Metabolic Networks and Their Structural Analysis

  2008cites this paper
• Exact Algorithms for Optimization and parameterized versions of some graph theoretic problems[HBNI Th 6]

  2008cites this paper
• Fast Monitoring Proximity and Centrality on Time-evolving Bipartite Graphs

  2008cites this paper
• Fast Molecular Shape Matching Using Contact Maps

  2007cites this paper
• The densest k-subgraph problem on clique graphs

  2007cites this paper
• Approximation algorithms for NP-hard problems in combinatorial optimization

  2007cites this paper
• Approximation Algorithms for NP-Hard Problems in Combinatorial Optimization

  2007cites this paper
• Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees

  2006cites this paper
• Parameterized Complexity of Neighborhood Problems in Graphs with no Small Cycles

  2006cites this paper
• Upper bounds and exact algorithms for p-dispersion problems

  2006cites this paper
• Triangles, 4-Cycles and Parameterized (In-)Tractability

  2006cites this paper
• Approximate k-Steiner Forests via the Lagrangian Relaxation Technique with Internal Preprocessing

  2006influential citation
• An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints

  2006cites this paper
• Different Formulations for Solving the Heaviest K-Subgraph Problem

  2005cites this paper