Deterministic Õ(n^{ω(σ)}) time algorithm for multi-source reachability in digraphs with n^σ sources, improving prior randomized n^{1+2/3ω(σ)} bound.
Dreyer and Fred S
4 Pith papers cite this work. Polarity classification is still indexing.
4
Pith papers citing it
verdicts
UNVERDICTED 4representative citing papers
Defines the transmission zero forcing number as the smallest initial vertex set that fills a graph via weight accumulation from multiple neighbors and computes it on standard graph classes.
The winner of the normal partizan domination game is determined for complete split graphs including star forests under arbitrary initial colorings.
The f-Critical Set problem is NP-complete on planar subcubic bipartite graphs with m(f)=2, W[1]-hard parameterized by treewidth alone, yet FPT parameterized by treewidth plus m(f) or Δ(G), with kernels of size O(k·m(f)) and O(k·Δ(G)).
citing papers explorer
-
Multi-Source Reachability in Near-Optimal Time
Deterministic Õ(n^{ω(σ)}) time algorithm for multi-source reachability in digraphs with n^σ sources, improving prior randomized n^{1+2/3ω(σ)} bound.
-
Transmission Zero Forcing
Defines the transmission zero forcing number as the smallest initial vertex set that fills a graph via weight accumulation from multiple neighbors and computes it on standard graph classes.
-
The Normal Domination Partizan Game in Stars
The winner of the normal partizan domination game is determined for complete split graphs including star forests under arbitrary initial colorings.
-
Parameterized complexity of the f-Critical Set problem
The f-Critical Set problem is NP-complete on planar subcubic bipartite graphs with m(f)=2, W[1]-hard parameterized by treewidth alone, yet FPT parameterized by treewidth plus m(f) or Δ(G), with kernels of size O(k·m(f)) and O(k·Δ(G)).