Achieves (2k/3)-approximation for girth in weighted graphs in Õ(m + n^{1+2/k}) time for every k≥2, improving prior partial results, plus new fine-grained lower bounds for unweighted girth approximation.
Finding topological subgraphs
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
verdicts
UNVERDICTED 5roles
background 1polarities
background 1representative citing papers
Improved (O(pw), Δ)-LDD for pathwidth-pw digraphs and O(tw log n) integrality gap for directed sparsest-cut LP on treewidth-tw graphs via refined quasipartition analysis.
A differentially private pipeline using node-level DP summaries to fit ERGMs or SBMs, generate synthetic networks, and simulate SIS disease spread on ARTNet sexual contact data produces incidence, prevalence, and intervention effect sizes close to non-private versions.
Wavelet forests extended with select support incur little space overhead and outperform or match standard wavelet trees on most tested inputs.
The paper overviews universal obstructions as a unifying framework for graph parameters, surveys existing results across many parameters, and offers some unifying classification results.
citing papers explorer
-
Tighter bounds for weighted and unweighted shortest cycle approximation
Achieves (2k/3)-approximation for girth in weighted graphs in Õ(m + n^{1+2/k}) time for every k≥2, improving prior partial results, plus new fine-grained lower bounds for unweighted girth approximation.
-
Directed Low Diameter Decomposition for Structured Digraphs
Improved (O(pw), Δ)-LDD for pathwidth-pw digraphs and O(tw log n) integrality gap for directed sparsest-cut LP on treewidth-tw graphs via refined quasipartition analysis.
-
Differentially Private Modeling of Disease Transmission within Human Contact Networks
A differentially private pipeline using node-level DP summaries to fit ERGMs or SBMs, generate synthetic networks, and simulate SIS disease spread on ARTNet sexual contact data produces incidence, prevalence, and intervention effect sizes close to non-private versions.
-
Wavelet Forests Revisited
Wavelet forests extended with select support incur little space overhead and outperform or match standard wavelet trees on most tested inputs.
-
An Overview of Universal Obstructions for Graph Parameters
The paper overviews universal obstructions as a unifying framework for graph parameters, surveys existing results across many parameters, and offers some unifying classification results.