<p>The densest subgraph problem is an important problem with both theoretical and practical significance. We consider a variant of the problem, the directed densest subgraph problem, under the partially dynamic setting of edge insertions only. We give a algorithm maintaining a (1-ε)-approximate directed densest subgraph in O(log<sup>3</sup>n/ε<sup>6</sup>) amortized time per edge insertion, based on earlier work by Chekuri and Quanrud. This result partially improves on an earlier result by Sawlani and Wang, which guarantees O(log<sup>5</sup>n/ε<sup>7</sup>) worst case time for edge insertions and deletions.</p>
| Identifer | oai:union.ndltd.org:purdue.edu/oai:figshare.com:article/22714027 |
| Date | 29 April 2023 |
| Creators | Richard Zou Li (15361858) |
| Source Sets | Purdue University |
| Detected Language | English |
| Type | Text, Thesis |
| Rights | CC BY 4.0 |
| Relation | https://figshare.com/articles/thesis/Approximate_Partially_Dynamic_Directed_Densest_Subgraph/22714027 |
Page generated in 0.0131 seconds