Export Citations
2 Results for: Keyword: neighborhood independence
Save this search
Please login to be able to save your searches and receive alerts for new content matching your search criteria.
Searched The ACM Guide to Computing Literature (3,796,870 records)|Limit your search to The ACM Full-Text Collection (767,726 records)
Select All
- research-articleJuly 2020Honorable Mention
A Unified Sparsification Approach for Matching Problems in Graphs of Bounded Neighborhood Independence
SPAA '20: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and ArchitecturesPages 395–406https://doi.org/10.1145/3350755.3400248The neighborhood independence number of a graph G, denoted by β = β(G), is the size of the largest independent set in the neighborhood of any vertex. Graphs with bounded neighborhood independence, already for constant β, constitute a wide family of ...
- research-articleSeptember 2019
Fully Dynamic Graph Algorithms Inspired by Distributed Computing: Deterministic Maximal Matching and Edge Coloring in Sublinear Update-Time
ACM Journal of Experimental Algorithmics (JEA), Volume 24Article No.: 1.14, Pages 1–24https://doi.org/10.1145/3338529We study dynamic graphs in the fully dynamic centralized setting. In this setting, the vertex set of size n of a graph G is fixed, and the edge set changes step-by-step, such that each step either adds or removes an edge. Dynamic graphs have various ...