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,097 | Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees | 2020 | VLDB | 9.1725037e-05 |
| 3,993 | Efficient k-Clique Listing: An Edge-Oriented Branching Strategy | 2024 | SIGMOD | 6.9688824e-05 |
| 5,556 | Fast Maximal Clique Enumeration on Uncertain Graphs: A Pivot-based Approach | 2022 | SIGMOD | 6.1751704e-05 |
| 7,226 | Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach | 2022 | VLDB | 5.6667372e-05 |
| 7,418 | Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale | 2022 | VLDB | 5.6236086e-05 |
| 10,100 | Parallel Colorful h-star Core Maintenance in Dynamic Graphs | 2023 | VLDB | 5.1488731e-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 |
|---|---|---|---|---|
| 189 | Querying K-Truss Community in Large and Dynamic Graphs | 2014 | SIGMOD | 0.00026114928 |
| 3,962 | Real-Time Multi-Criteria Social Graph Partitioning: A Game Theoretic Approach | 2015 | SIGMOD | 6.9865803e-05 |
| 4,474 | Querying Big Graphs within Bounded Resources | 2014 | SIGMOD | 6.6803983e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 4,672 | Efficient Maximum k-Defective Clique Computation with Improved Time Complexity | 2023 | SIGMOD |
| 2 | 9,387 | Efficient Algorithms for Pseudoarboricity Computation in Large Static and Dynamic Graphs | 2024 | VLDB |
| 3 | 6,268 | Theoretically and Practically Efficient Maximum Defective Clique Search | 2024 | SIGMOD |
| 4 | 11,198 | Constant-time Connectivity Querying in Dynamic Graphs | 2024 | SIGMOD |
| 5 | 2,826 | Hierarchical Core Maintenance on Large Dynamic Graphs | 2021 | VLDB |
| 6 | 7,578 | Minimum Strongly Connected Subgraph Collection in Dynamic Graphs | 2024 | VLDB |
| 7 | 5,697 | Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs | 2021 | VLDB |
| 8 | 10,100 | Parallel Colorful h-star Core Maintenance in Dynamic Graphs | 2023 | VLDB |
| 9 | 9,060 | Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms | 2023 | PODS |
| 10 | 11,505 | Quasi-stable Coloring for Graph Compression | 2023 | VLDB |