Exact algorithms for problems related to the densest \(k\)-set problem

DOI10.1016/j.ipl.2014.04.009zbMath1302.05182OpenAlexW1970964752MaRDI QIDQ2448865

Guan-Han Wu, Maw-Shang Chang, Li-Hsuan Chen, Ling-Ju Hung, Peter Rossmanith

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

zbMATH Keywords

design of algorithmsexact algorithmpartial vertex coverdensest (sparsest) \(k\)-setminimum (maximum) \(k\)-vertex cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Complexity and approximability of the happy set problem ⋮ Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem ⋮ Graph classes and approximability of the happy set problem ⋮ An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems

Cites Work

• Exact exponential algorithms.
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Sort and Search: exact algorithms for generalized domination
• Clustering and domination in perfect graphs
• Faster algorithms for computing power indices in weighted voting games
• The densest \(k\)-subgraph problem on clique graphs
• Parameterized complexity of Vertex Cover variants
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Finding Dense Subgraphs with Size Bounds
• On Finding Dense Subgraphs
• A Fast Parametric Maximum Flow Algorithm and Applications
• Exact and Approximation Algorithms for Densest k-Subgraph
• Improved Upper Bounds for Partial Vertex Cover
• Unnamed Item
• Unnamed Item

This page was built for publication: Exact algorithms for problems related to the densest \(k\)-set problem