Showing cs.DSShow all
2 papers · 1 filter
cs.DS2025
New Distributed Interactive Proofs for Planarity: A Matter of Left and Right
Yuval Gil, Merav Parter
We provide new distributed interactive proofs (DIP) for planarity and related graph families. The notion of a \emph{distributed interactive proof} (DIP) was introduced by Kol, Oshm…
cs.DS2024
Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs
Yuval Gil
We design new deterministic CONGEST approximation algorithms for \emph{maximum weight independent set (MWIS)} in \emph{sparse graphs}. As our main results, we obtain new -a…