Improved Time Complexity of Bandwidth Approximation in Dense Graphs

MaRDI QIDQ6236841FDOQ6236841

Authors: Hao-Hsiang Hung 

Publication date: 1 November 2012

Abstract: Given a graph $G=(V,E)$ and and a proper labeling $f$ from $V$ to $1,\mathrm{...},n$, we define $B(f)$ as the maximum absolute difference between $f(u)$ and $f(v)$ where $(u,v)inE$. The bandwidth of $G$ is the minimum $B(f)$ for all $f$. Say $G$ is $delta$-dense if its minimum degree is $deltan$. In this paper, we investigate the trade-off between the approximation ratio and the time complexity of the classical approach of Karpinski {et al}.cite{Karpin97}, and present a faster randomized algorithm for approximating the bandwidth of $delta$-dense graphs. In particular, by removing the polylog factor of the time complexity required to enumerate all possible placements for balls to bins, we reduce the time complexity from $O(n^{6}cdot(logn{)}^{O(1)})$ to $O(n^{4+o(1)})$. In advance, we reformulate the perfect matching phase of the algorithm with a maximum flow problem of smaller size and reduce the time complexity to $O(n^{2}loglogn)$. We also extend the graph classes could be applied by the original approach: we show that the algorithm remains polynomial time as long as $delta$ is $O({(loglogn)}^2/logn)$.

This page was built for publication: Improved Time Complexity of Bandwidth Approximation in Dense Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6236841)