6533b7cffe1ef96bd12582c4

RESEARCH PRODUCT

Fast Algorithms for Pseudoarboricity

Markus Blumenstock

subject

Binary search algorithmComputation0102 computer and information sciences02 engineering and technologyOrientation (graph theory)01 natural sciencesFlow (mathematics)010201 computation theory & mathematicsLog-log plotTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY0202 electrical engineering electronic engineering information engineeringGraph (abstract data type)020201 artificial intelligence & image processingUnit (ring theory)AlgorithmTime complexityMathematicsofComputing_DISCRETEMATHEMATICSMathematics

description

The densest subgraph problem, which asks for a subgraph with the maximum edges-to-vertices ratio d∗, is solvable in polynomial time. We discuss algorithms for this problem and the computation of a graph orientation with the lowest maximum indegree, which is equal to ⌈d∗⌉. This value also equals the pseudoarboricity of the graph. We show that it can be computed in O(|E| √ log log d∗) time, and that better estimates can be given for graph classes where d∗ satisfies certain asymptotic bounds. These runtimes are achieved by accelerating a binary search with an approximation scheme, and a runtime analysis of Dinitz’s algorithm on flow networks where all arcs, except the source and sink arcs, have unit capacity. We experimentally compare implementations of various algorithms for the densest subgraph and pseudoarboricity problems. In flow-based algorithms, Dinitz’s algorithm performs significantly better than push-relabel algorithms on all instances tested.

yearjournalcountryeditionlanguage
2015-12-302016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX)
https://doi.org/10.1137/1.9781611974317.10