Can I read A Constructive Arboricity Approximation Scheme on EtoBox?

A Constructive Arboricity Approximation Scheme by Blumenstock, Markus; Fischer, Frank is a scholarly article available to read on EtoBox.

What is A Constructive Arboricity Approximation Scheme about?

The arboricity $\Gamma$ of a graph is the minimum number of forests its edge set can be partitioned into. Previous approximation schemes were nonconstructive, i.e., they only approximated the arboricity as a value without computing a corresponding forest partition. This is because they operate on the related pseudoforest partitions or the dual problem of finding dense subgraphs. We propose an algorithm for converting a partition of $k$ pseudoforests into a partition of $k+1$ forests in $O(mk\log k + m \log n)$ time with a data structure by Brodal and Fagerberg that stores graphs of arboricity $k$. A slightly better bound can be given when perfect hashing is used. When applied to a pseudoforest partition obtained from Kowalik's approximation scheme, our conversion implies a constructive $(1+\epsilon)$-approximation algorithm with runtime $O(m \log n \log \Gamma\, \epsilon^{-1})$ for every $\epsilon > 0$. For fixed $\epsilon$, the runtime can be reduced to $O(m \log n)$. Our conversion also implies a near-exact algorithm that computes a partition into at most $\Gamma+2$ forests in $O(m\log n \,\Gamma \log^* \Gamma)$ time. It might also pave the way to faster exact arboricity algorith

Author

Blumenstock, Markus; Fischer, Frank

Published

2018

Language

EN