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

DOI10.1016/J.IPL.2014.04.009MaRDI QIDQ2448865zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

exact algorithmdesign of algorithmspartial vertex coverdensest (sparsest) \(k\)-setminimum (maximum) \(k\)-vertex cover

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 26490 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• A Fast Parametric Maximum Flow Algorithm and Applications
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Clustering and domination in perfect graphs
• Exact and approximation algorithms for densest \(k\)-subgraph (extended abstract)
• Exact exponential algorithms.
• Faster algorithms for computing power indices in weighted voting games
• Finding Dense Subgraphs with Size Bounds
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Improved Upper Bounds for Partial Vertex Cover
• On Finding Dense Subgraphs
• Parameterized complexity of Vertex Cover variants
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Sort and Search: exact algorithms for generalized domination
• The densest \(k\)-subgraph problem on clique graphs

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)