PTAS for densest \(k\)-subgraph in interval graphs

DOI10.1007/s00453-014-9956-7zbMath1336.68300OpenAlexW2161076233MaRDI QIDQ261389

Tim Nonner

Publication date: 23 March 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-014-9956-7

zbMATH Keywords

approximation schemesgraph algorithmsapproximation algorithmsinterval graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (5)

Approximation of the Quadratic Knapsack Problem ⋮ 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 ⋮ On solving the densestk-subgraph problem on large graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Constant factor approximation algorithms for the densest \(k\)-subgraph problem on proper interval graphs and bipartite permutation graphs
• A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
• Clustering and domination in perfect graphs
• Geometric algorithms and combinatorial optimization
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• The densest \(k\)-subgraph problem on clique graphs
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
• Detecting high log-densities
• Densest k-Subgraph Approximation on Intersection Graphs
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Approximating the Sparsest k-Subgraph in Chordal Graphs
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Greedily Finding a Dense Subgraph
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• The dense \(k\)-subgraph problem

This page was built for publication: PTAS for densest \(k\)-subgraph in interval graphs