Exact algorithms for problems related to the densest k-set problem
DOI10.1016/J.IPL.2014.04.009zbMATH Open1302.05182OpenAlexW1970964752MaRDI QIDQ2448865FDOQ2448865
Authors: Maw-Shang Chang, Li-Hsuan Chen, Ling-Ju Hung, Peter Rossmanith, Guan-Han Wu 
Publication date: 5 May 2014
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2014.04.009
Recommendations
- Exact and approximation algorithms for densest \(k\)-subgraph (extended abstract)
- A deterministic approximation algorithm for the densest \(k\)-subgraph problem
- Algorithms for the densest sub-lattice problem
- An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem
- scientific article; zbMATH DE number 176777
- Algorithms for the densest subgraph with at least \(k\) vertices and with a specified subset
- Approximating the dense set-cover problem
- Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
- Graph-Theoretic Concepts in Computer Science
- Exact algorithms for dominating set
exact algorithmdesign of algorithmspartial vertex coverdensest (sparsest) \(k\)-setminimum (maximum) \(k\)-vertex cover
Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Exact exponential algorithms.
- Clustering and domination in perfect graphs
- The densest \(k\)-subgraph problem on clique graphs
- Parameterized complexity of Vertex Cover variants
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- On Finding Dense Subgraphs
- Exact and approximation algorithms for densest \(k\)-subgraph (extended abstract)
- Improved Upper Bounds for Partial Vertex Cover
- A new algorithm for optimal 2-constraint satisfaction and its implications
- A Fast Parametric Maximum Flow Algorithm and Applications
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Title not available (Why is that?)
- Finding Dense Subgraphs with Size Bounds
- Sort and Search: exact algorithms for generalized domination
- Faster algorithms for computing power indices in weighted voting games
Cited In (5)
- Graph classes and approximability of the happy set problem
- Complexity and approximability of the happy set problem
- Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
- An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
- Algorithmic construction of sets for k -restrictions
This page was built for publication: Exact algorithms for problems related to the densest \(k\)-set problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2448865)
