Cover Image

Differentially private graph coloring

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Xie, Michael, Wu, Jiayi, Nguyen, Dung, Srinivasan, Aravind
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Controlling the Spread of Epidemics on Networks with Differential Privacy
by: Nguyen, Dung, et al.
Published: (2025)

Differentially private exact recovery for stochastic block models
by: Nguyen, Dung, et al.
Published: (2024)

Online Dependent Rounding Schemes for Bipartite Matchings, with Applications
by: Joseph, et al.
Published: (2023)

Barter Exchange with Shared Item Valuations
by: Luque, Juan, et al.
Published: (2024)

Dependent randomized rounding for clustering and partition systems with knapsack constraints
by: Harris, David G., et al.
Published: (2017)

Edge-coloring sparse graphs with $Δ$ colors in quasilinear time
by: Kowalik, Lukasz
Published: (2024)

Proportionally Fair Matching via Randomized Rounding
by: Duppala, Sharmila, et al.
Published: (2024)

Concentration of Submodular Functions and Read-k Families Under Negative Dependence
by: Duppala, Sharmila, et al.
Published: (2023)

Dimension-Free Correlated Sampling for the Hypersimplex
by: Joseph, et al.
Published: (2025)

Comparative genomics with succinct colored de Bruijn graphs
by: Ramos, Lucas P., et al.
Published: (2024)

Stochastic Optimization and Learning for Two-Stage Supplier Problems
by: Brubach, Brian, et al.
Published: (2020)

Solving Linear Programs with Differential Privacy
by: Ene, Alina, et al.
Published: (2025)

Solving Positive Linear Programs with Differential Privacy
by: Ene, Alina, et al.
Published: (2026)

Differentially Private Densest Subgraph Detection
by: Nguyen, Dung, et al.
Published: (2021)

An FPT algorithm for Matching Cut and d-cut
by: Aravind, N R, et al.
Published: (2021)

Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes
by: Brubach, Brian, et al.
Published: (2021)

Kernelization for list $H$-coloring for graphs with small vertex cover
by: Piecyk, Marta, et al.
Published: (2025)

Better coloring of 3-colorable graphs
by: Kawarabayashi, Ken-ichi, et al.
Published: (2024)

Approximating optimization problems in graphs with locational uncertainty
by: Bougeret, Marin, et al.
Published: (2022)

Coloring tournaments with few colors: Algorithms and complexity
by: Klingelhoefer, Felix, et al.
Published: (2023)

Finding $b$-colorings Using Feedback Edges
by: Balabán, Jakub
Published: (2025)

Almost Tight Bounds for Differentially Private Densest Subgraph
by: Dinitz, Michael, et al.
Published: (2023)

Dynamic O(arboricity) coloring in polylogarithmic worst-case time
by: Ghaffari, Mohsen, et al.
Published: (2024)

Improved linearly ordered colorings of hypergraphs via SDP rounding
by: Louis, Anand, et al.
Published: (2024)

Almost linear time differentially private release of synthetic graphs
by: Liu, Jingcheng, et al.
Published: (2024)

Adaptive Power Iteration Method for Differentially Private PCA
by: Nguyen, Ta Duy, et al.
Published: (2026)

Parameterized Complexity of Path Set Packing
by: Aravind, N. R., et al.
Published: (2022)

A characterization of one-sided error testable graph properties in bounded degeneracy graphs
by: Lachish, Oded, et al.
Published: (2026)

A Generalized Binary Tree Mechanism for Differentially Private Approximation of All-Pair Distances
by: Dinitz, Michael, et al.
Published: (2025)

Approximating maximum properly colored forests via degree bounded independent sets
by: Bai, Yuhang, et al.
Published: (2025)

On Differentially Private Linear Algebra
by: Kaplan, Haim, et al.
Published: (2024)

An Improved Pseudopolynomial Time Algorithm for Subset Sum
by: Chen, Lin, et al.
Published: (2024)

A Note on Deterministic FPTAS for Partition
by: Chen, Lin, et al.
Published: (2025)

A Nearly Quadratic-Time FPTAS for Knapsack
by: Chen, Lin, et al.
Published: (2023)

Approximating Partition in Near-Linear Time
by: Chen, Lin, et al.
Published: (2024)

Weakly Approximating Knapsack in Subquadratic Time
by: Chen, Lin, et al.
Published: (2025)

The trace reconstruction problem for spider graphs
by: Sun, Alec, et al.
Published: (2022)

The Canadian Traveller Problem on outerplanar graphs
by: Beaudou, Laurent, et al.
Published: (2024)

Private graph colouring with limited defectiveness
by: Christiansen, Aleksander B. G., et al.
Published: (2024)

Practical algorithms for Hierarchical overlap graphs
by: Talera, Saumya, et al.
Published: (2024)