The densest subgraph problem with a convex/concave size function

DOI10.1007/s00453-017-0400-7zbMath1401.05171arXiv1703.03603OpenAlexW2776104937MaRDI QIDQ1799206

Atsushi Miyauchi, Yasushi Kawase

Publication date: 18 October 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1703.03603

zbMATH Keywords

graphsapproximation algorithmsdense subgraph extractiondensest subgraph problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Signed and weighted graphs (05C22) Density (toughness, etc.) (05C42)

Related Items (7)

Covering a graph with densest subgraphs ⋮ Extracting densest sub-hypergraph with convex edge-weight functions ⋮ A study on modularity density maximization: column generation acceleration and computational complexity analysis ⋮ Finding densest \(k\)-connected subgraphs ⋮ In search of the densest subgraph ⋮ Top-\(k\) overlapping densest subgraphs: approximation algorithms and computational complexity ⋮ Computing the \(k\) densest subgraphs of a graph

Uses Software

• MotifCut
• MCODE

Cites Work

• Unnamed Item
• Submodular functions and optimization.
• Detecting high log-densities
• Finding Dense Subgraphs with Size Bounds
• On Finding Dense Subgraphs
• Combinatorial Optimization with Rational Objective Functions
• The Densest Subgraph Problem with a Convex/Concave Size Function
• Greedily Finding a Dense Subgraph
• Discounted average degree density metric and new algorithms for the densest subgraph problem
• An $o(n^3 )$-Time Maximum-Flow Algorithm
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• The dense \(k\)-subgraph problem

This page was built for publication: The densest subgraph problem with a convex/concave size function