A simple greedy algorithm for dynamic graph orientation

Research output: Contribution to book/anthology/report/proceedingArticle in proceedings

Documents

DOI

Graph orientations with low out-degree are one of several ways to efficiently store sparse graphs. If the graphs allow for insertion and deletion of edges, one may have to flip the orientation of some edges to prevent blowing up the maximum out-degree. We use arboricity as our sparsity measure. With an immensely simple greedy algorithm, we get parametrized trade-off bounds between out-degree and worst case number of flips, which previously only existed for amortized number of flips. We match the previous best worst-case algorithm (in O(log n) flips) for general arboricity and beat it for either constant or super-logarithmic arboricity. We also match a previous best amortized result for at least logarithmic arboricity, and give the first results with worst-case O(1) and O(sqrt(log n)) flips nearly matching degree bounds to their respective amortized solutions.
Original languageEnglish
Title of host publication28th International Symposium on Algorithms and Computation (ISAAC 2017)
EditorsYoshio Okamoto , Takeshi Tokuyama
Number of pages11
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication year2017
Pages12:1-12:12
ISBN (Electronic)978-3-95977-054-5
DOIs
StatePublished - 2017
Event28th International Symposium on Algorithms and Computation - Cape Panwa Hotel, Phuket, Thailand
Duration: 9 Dec 201712 Dec 2017
Conference number: 28
https://saki.siit.tu.ac.th/isaac2017/

Conference

Conference28th International Symposium on Algorithms and Computation
Nummer28
LocationCape Panwa Hotel
LandThailand
ByPhuket
Periode09/12/201712/12/2017
Internetadresse
SeriesLeibniz International Proceedings in Informatics
Number92
ISSN1868-8969

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 120486564