Effective and Efficient Dynamic Graph Coloring
Summary: Incrementally maintains dynamic-graph colorings while matching the quality of strong static large-graph colorers. A color-propagation algorithm, color index, and pruning rules restrict updates to a small neighborhood, improving efficiency. (summarized by gpt-5.6-luna on Jul 24 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Long Yuan (University of New South Wales)
- 2. Lu Qin (University of Technology Sydney)
- 3. Xuemin Lin (University of New South Wales)
- 4. Lijun Chang (University of Sydney)
- 5. Wenjie Zhang (University of New South Wales)
BibTeX Citation
@article{yuan_vldb18,
title = {{Effective and Efficient Dynamic Graph Coloring}},
author = {Yuan, Long and Qin, Lu and Lin, Xuemin and Chang, Lijun and Zhang, Wenjie},
journal = {PVLDB},
series = {{VLDB} '18},
volume = {11},
number = {3},
pages = {338--351},
doi = {10.14778/3157794.3157802},
url = {https://doi.org/10.14778/3157794.3157802},
year = {2018}
}
Incoming Citations (Sorted by Pagerank)
Showing 6 of 6 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,141 | Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees | 2020 | VLDB | 8.9668034e-05 |
| 3,610 | Efficient k-Clique Listing: An Edge-Oriented Branching Strategy | 2024 | SIGMOD | 7.1643588e-05 |
| 4,732 | Fast Maximal Clique Enumeration on Uncertain Graphs: A Pivot-based Approach | 2022 | SIGMOD | 6.4461271e-05 |
| 7,248 | Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale | 2022 | VLDB | 5.5746656e-05 |
| 7,377 | Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach | 2022 | VLDB | 5.5395908e-05 |
| 10,327 | Parallel Colorful h-star Core Maintenance in Dynamic Graphs | 2023 | VLDB | 5.0333462e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 3 of 3 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 184 | Querying K-Truss Community in Large and Dynamic Graphs | 2014 | SIGMOD | 0.00026100147 |
| 4,042 | Real-Time Multi-Criteria Social Graph Partitioning: A Game Theoretic Approach | 2015 | SIGMOD | 6.835891e-05 |
| 4,551 | Querying Big Graphs within Bounded Resources | 2014 | SIGMOD | 6.5401646e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 9,571 | Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs | 2024 | VLDB |
| 2 | 5,552 | Theoretically and Practically Efficient Maximum Defective Clique Search | 2024 | SIGMOD |
| 3 | 11,540 | Constant-time Connectivity Querying in Dynamic Graphs | 2024 | SIGMOD |
| 4 | 2,869 | Hierarchical Core Maintenance on Large Dynamic Graphs | 2021 | VLDB |
| 5 | 10,770 | Counting HyperGraphlets via Color Coding: a Quadratic Barrier and How to Break It | 2026 | VLDB |
| 6 | 7,724 | Minimum Strongly Connected Subgraph Collection in Dynamic Graphs | 2024 | VLDB |
| 7 | 5,720 | Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs | 2021 | VLDB |
| 8 | 10,327 | Parallel Colorful h-star Core Maintenance in Dynamic Graphs | 2023 | VLDB |
| 9 | 9,238 | Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms | 2023 | PODS |
| 10 | 11,814 | Quasi-stable Coloring for Graph Compression | 2023 | VLDB |