Pith. sign in

REVIEW 4 major objections 5 minor 28 references

Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs

T0 review · 4 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For any fixed surface genus, Minimum Dominating Set can be approximated within 34+ε in a constant number of LOCAL rounds.

desk verdict A genuinely new reduction for MDS on bounded-genus graphs, but the headline 34+ε depends on an unproved uniformity claim in a cited paper—worth refereeing with a required fix. read the letter →

arxiv 2507.04960 v1 pith:4Z5A6263 submitted 2025-07-07 cs.DC cs.DS

Marthe Bonamy , Cyril Gavoille , Timothé Picavet , Alexandra Wesolek This is my paper · ORCID
classification cs.DCcs.DS MSC 68W1568R1005C6905C10
keywords distributedalgorithmLOCALmodelminimumdominatingsetboundedgenusgraphsasymptoticdimensionuniformapproximationplanarconstant-round
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes that Minimum Dominating Set (MDS) on graphs embeddable in a surface of bounded Euler genus $g$ admits a deterministic constant-round distributed approximation in the LOCAL model, with approximation ratio $34+\varepsilon$, independent of $g$. This improves on previous algorithms whose ratio grew like $\Omega(\sqrt{g})$ with genus, and on the $91+\varepsilon$ ratio known only for orientable surfaces. The proof is short and modular: it converts any planar MDS algorithm with a 'uniform' approximation guarantee into an algorithm for bounded-genus graphs, using only the fact that bounded-genus graphs have asymptotic dimension at most two and that their local non-planarities are sparse. The same conversion yields a $906$-approximation from a simple self-contained planar $302$-approximation, and extends to any graph class of bounded asymptotic dimension that is locally planar or locally bounded-genus.

What carries the argument

The load-bearing mechanism is the generic conversion algorithm $B$ (Proposition 3). It colors the power graph $G^{2k+2}$ with $d+1$ colors so that each monochromatic component has weak diameter bounded by the control function $f(2k+2)$, then runs the uniform planar algorithm $A$ on each component while excluding the $T$-error set $X$ of vertices whose radius-$T$ ball is not planar; a final brute-force step dominates the remaining region $N^2[X]$, whose connected components have weak diameter bounded by $g(2T+5)$ via Euler-genus additivity (Claim 4). The key notion that makes composition work is $k$-uniform approximation: for every subset $S$, the algorithm selects at most $\alpha \cdot \mathrm{MDS}(G,N^k[S])$ vertices inside $S$, which localizes the approximation guarantee and lets it survive the coloring decomposition.

What would settle it

Run the planar algorithm of [HKOdM+25] on a planar graph $G$ and a subset $S$; if for some $\varepsilon>0$ the algorithm outputs more than $(11+\varepsilon)\cdot \mathrm{MDS}(G,N^7[S])$ vertices of $S$, then Observation 1 is false and Theorem 1's $34+\varepsilon$ ratio loses its planar ingredient. Alternatively, exhibit an Euler genus-$g$ graph where the output of algorithm $B$ exceeds $(34+\varepsilon)\cdot \mathrm{MDS}(G)$, which would refute Theorem 1 directly.

Watch

Extended reading notes

Core claim

The paper's main theorem states that for every $\varepsilon>0$ and every $g$, there is a $7$-uniform $(34+\varepsilon)$-approximation LOCAL algorithm for Minimum Dominating Set in Euler genus-$g$ graphs, with round complexity $C(\varepsilon,g)$ for some function $C$. In other words, the approximation ratio no longer depends on the genus at all, and the round complexity depends only on the fixed parameters $\varepsilon$ and $g$, not on the number of vertices. The central instrument is a generic algorithm $B$ that takes any $k$-uniform $\alpha$-approximation for a hereditary class $\mathcal{C}$ and lifts it to a class $\mathcal{D}$ of asymptotic dimension $d$: the lifted algorithm achieves $(\alpha(d+1)+1)$-approximation, or $\alpha(d+1)$ if $\mathcal{D}$ is locally $\mathcal{C}$, with round complexity controlled by the dimension's control function plus the weak diameter of the 'error' vertices whose local ball leaves $\mathcal{C}$. Applied to planar graphs and Euler genus-$g$ graphs, with the observation that the known $(11+\varepsilon)$ planar algorithm of [HKOdM+25] is $7$-uniform, this yields the $34+\varepsilon$ ratio.

Load-bearing premise

The result's sharpest ratio inherits the unproved claim, stated as Observation 1, that the known $(11+\varepsilon)$-approximation LOCAL algorithm for planar graphs is $7$-uniform; if that uniformity failed, the $34+\varepsilon$ bound would not follow, though the paper's own $906$-approximation would remain intact.

Editorial extensions

If this is right

  • For every fixed genus $g$, MDS on bounded-genus graphs is approximable within $34+\varepsilon$ in $C(\varepsilon,g)$ rounds, independent of $n$ and of $g$; this removes the previous $\Omega(\sqrt{g})$ growth in the ratio.
  • The orientable-only $91+\varepsilon$ bound is improved for all Euler genus graphs, including non-orientable surfaces.
  • The generic proposition gives a $35(d+1)$-approximation in $C(d,g,r)$ rounds for any graph class of asymptotic dimension $d$ that is locally of Euler genus $g$.
  • The simple self-contained planar $302$-approximation already yields a $906$-approximation for bounded-genus graphs, giving a short proof independent of the fine analysis in [HKOdM+25].
  • Conjecture 1 proposes that the ratio can be pushed down to $7$ for bounded-genus graphs, matching the planar constant.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the uniformity property is the real bottleneck, any future improvement of the planar uniform ratio automatically improves the bounded-genus ratio through the same pipeline, without revisiting the genus argument.
  • The same decomposition may apply to other covering and domination variants in classes with bounded local treewidth, since the brute-force step over constant-radius neighborhoods remains polynomial there.
  • The $906$ version is a robustness certificate: even if Observation 1 fails, the structural reduction from bounded genus to planar uniform algorithms still stands.
  • One could test the algorithm empirically on random triangulations and genus-$g$ grids to see whether the actual approximation ratio is closer to the planar constant than to $34$.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper studies deterministic LOCAL algorithms for Minimum Dominating Set (MDS) on graphs of bounded Euler genus and, more generally, on graph classes of bounded asymptotic dimension that are locally contained in a nicer class. Its main technical tool is Proposition 3, which converts a k-uniform α-approximation algorithm for a hereditary class C into an (α(d+1)+1)-approximation algorithm for a class D of asymptotic dimension d, with round complexity T+δ+2, where δ is controlled by the weak diameter of the error set. Specializing to planar C and Euler genus-g D gives, via the paper's new 4-uniform 302-approximation algorithm for planar graphs (Proposition 5), a 906-approximation, though the arithmetic in Proposition 3 actually yields 907 in the presence of errors. If one additionally accepts Observation 1, which asserts that the planar algorithm of [HKOdM+25, Theorem 2.3] is 7-uniform with ratio 11+ε, then Theorem 1 yields a 7-uniform (34+ε)-approximation for Euler genus-g graphs with f(g,ε) rounds. Theorem 2 extends the same idea to classes locally of Euler genus g. The paper is a short proof of a general reduction rather than an exhaustive algorithmic engineering study.

Significance. If Observation 1 were proved and the proof of Proposition 5 completed, the paper would deliver a genuinely simple and reusable reduction: any uniform local planar approximation can be lifted to bounded-genus graphs and, more generally, to bounded-asymptotic-dimension classes. The 34+ε ratio would improve on the previous 24g+O(1) bound (which is linear in g) and on the 91+ε bound for orientable surfaces. The genus-additivity argument in Claim 4 is clean and self-contained, and Proposition 3's proof is mostly transparent. I also view as a strength that the paper explicitly identifies the load-bearing external assumption in Observation 1 rather than hiding it, and it does not fit constants to data. The main limitation is that the strongest advertised quantitative result currently rests on an unproved uniformity assertion, and the self-contained 302-approximation proof is too compressed to verify.

major comments (4)
  1. [Section 3, Observation 1 and Theorem 1] Observation 1 is load-bearing for Theorem 1 and is stated without proof; the text explicitly says that the uniformity of [HKOdM+25, Theorem 2.3] is not explicitly stated in their paper. The parameter k=7 enters Proposition 3 both through T=f(2k+2)+max{k+1,r} and through the proof's equality MDS(G,N^k_G[C])=MDS(G_v,N^k_{G_v}[C]), which requires the external algorithm to satisfy the subset-uniform bound |A(H)∩C|≤(11+ε)MDS(H,N^k_H[C]) for every induced sub-instance H∈C. A global (11+ε)-approximation for planar graphs does not imply that bound. Please provide a complete proof of Observation 1 or cite a theorem in [HKOdM+25] that establishes it; without this, Theorem 1 is not supported.
  2. [Abstract and Section 3, 'Our contributions'] The abstract and Section 3 claim a 906-approximation from Proposition 5, but Proposition 3's formula is α(d+1)+1; with α=302 and d=2 this is 907 whenever the T-error set X is nonempty, which is the generic case for Euler genus g>0. The value 906 corresponds to the error-free case X=∅. Please correct the arithmetic or state explicitly that 906 is the no-error ratio and 907 is the general ratio; the same discrepancy should be reconciled with the abstract's 'α ≤ 906'.
  3. [Section 5, Claim 6 and Proposition 5] The proof of Claim 6 is too compressed to be verifiable and contains several unstated steps. Step 2 of Algorithm 2 refers to 'N^3[S]' although S is not an input of the algorithm; the 'first key observation' bounding the number of candidates for v_u by 2^{|C|}·MDS(G,B∪C) is asserted without proof; and the face-by-face counting leading to '3·2^5=96' choices per face and 'at most 3|X| options for f' is not derived. This proof underlies the self-contained 907/906-approximation, so it needs to be written out in full detail.
  4. [Section 4, proof of Proposition 3, k-uniformity of B] The k-uniformity proof for B at the end of Section 4 is not correct as stated. The argument says that if the brute-force set's intersection with W were smaller than MDS(G,N_G[W]), replacing it by a minimum dominating set of N_G[W] would yield a smaller dominating set; replacing a smaller set by a larger one cannot decrease the size, and it is not shown that the replacement still dominates V(G)\N[S]. Please supply a rigorous proof of the uniform bound |B(G)∩W| ≤ (α(d+1)+1)MDS(G,N^k_G[W]), or modify the algorithm and proof accordingly.
minor comments (5)
  1. [Section 5, Algorithm 2] Step 2 of Algorithm 2 refers to 'N^3[S]' although S is not an input of the algorithm; this should be 'N^3[u]'.
  2. [Section 1] There is a typo: 'embedds' should be 'embeds'.
  3. [Footnote 5] Footnote 5 contains grammatical errors and a hard-to-parse sentence; please rewrite it for clarity.
  4. [Theorem 2] Theorem 2 states a 35(d+1)-approximation, while the derivation via Proposition 2 gives (34+ε)(d+1); the exact dependence on ε should be stated.
  5. [Claim 4, Section 3] Claim 4 states the bound δ<g(2T+5) for g≥1; please state explicitly how the g=0 case is handled, since for planar graphs the error set is empty and the ratio is α(d+1).

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the main reduction is self-contained; the advertised 34+ε ratio rests on an unproved external observation in Observation 1, which is a correctness gap rather than a circular reduction.

full rationale

The derivation chain is not circular. Proposition 5 (4-uniform 302-approximation for planar graphs) is proved self-contained in Section 5. Proposition 3, the generic reduction from k-uniform planar algorithms to bounded-asymptotic-dimension classes, is proved in Section 4 with explicit inequalities and a detailed round-counting argument; it adapts rather than imports [BGPW25, Proposition 3.1], and Theorem 1 uses Proposition 3 directly. The 906-approximation and the composition with the asymptotic-dimension bound from [BBE+24, Theorem 1.9] rely on external published theorems, not on restatements of the target result. The only serious flagged gap is Observation 1 (Section 3): the paper states 'Although it is not explicitly stated in their paper, we can observe the following' and supplies no proof that [HKOdM+25, Theorem 2.3] is 7-uniform. That assertion is load-bearing for the 34+ε improvement, since the uniformity parameter k enters Proposition 3's bound and the local dominance comparisons. But this is an unproved external claim about another paper's algorithm, not an input redefined as an output, so it is a completeness and correctness concern, not circularity. The self-citations to [BBE+24] and [BGPW25] involve overlapping authors, but they are used for background and for the secondary Theorem 2; the main Theorem 1 does not depend on them. Score 2 reflects the minor self-citation and the flagged omission, not a circular derivation.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No numerical parameters are fitted to data; the constants 302, 907/906, 34, and 35 are derived in proofs. The paper leans on external theorems: asymptotic dimension of bounded-genus graphs from BBE+24, additivity of Euler genus from MT01, and a uniformity property of the HKOdM+25 algorithm. No new entities are postulated.

assumptions (4)
  • domain assumption Euler genus-g graphs have asymptotic dimension at most 2, with a 2-dimensional control function f(x) ≤ c(g)·x.
    Invoked in Section 3 before Theorem 1 and cited to [BBE+24, Theorem 1.9]. It sets d=2 in Proposition 3 and is not proved in this paper.
  • domain assumption The [HKOdM+25, Theorem 2.3] planar algorithm is a 7-uniform (11+ε)-approximation LOCAL algorithm.
    Stated in Section 3, Observation 1, explicitly said not to appear in the cited paper, and essential for the 34+ε ratio of Theorem 1.
  • standard math Euler genus is additive over pairwise disjoint subgraphs.
    Used in Claim 4 to bound the weak diameter δ; cited to [MT01, Theorem 4.4.3].
  • domain assumption Bounded-genus graphs have bounded local treewidth, so an optimal MDS on constant-radius balls can be computed in polynomial time via monadic second-order logic.
    Used in Section 3 and Section 4 to justify Step 4 of Algorithm 1; the LOCAL model allows unbounded computation, but polynomial-time execution needs this structural argument.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs." pith.science (2026). https://pith.science/paper/4Z5A6263

@misc{pith2026250704960,
  author       = {Pith},
  title        = {Pith review of: Distributed Approximation Algorithms for Minimum Dominating Set in Locally Nice Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4Z5A6263}},
  note         = {Machine review of arXiv:2507.04960}
}
abstract

We give a new, short proof that graphs embeddable in a given Euler genus-$g$ surface admit a simple $f(g)$-round $\alpha$-approximation distributed algorithm for Minimum Dominating Set (MDS), where the approximation ratio $\alpha \le 906$. Using tricks from Heydt et al. [European Journal of Combinatorics (2025)], we in fact derive that $\alpha \le 34 +\varepsilon$, therefore improving upon the current state of the art of $24g+O(1)$ due to Amiri et al. [ACM Transactions on Algorithms (2019)]. It also improves the approximation ratio of $91+\varepsilon$ due to Czygrinow et al. [Theoretical Computer Science (2019)] in the particular case of orientable surfaces. All our distributed algorithms work in the deterministic LOCAL model. They do not require any preliminary embedding of the graph and only rely on two things: a LOCAL algorithm for MDS on planar graphs with ``uniform'' approximation guarantees and the knowledge that graphs embeddable in bounded Euler genus surfaces have asymptotic dimension $2$. More generally, our algorithms work in any graph class of bounded asymptotic dimension where ``most vertices'' are locally in a graph class that admits a LOCAL algorithm for MDS with uniform approximation guarantees.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 6 canonical work pages

  1. [1]

    Auslander, T

    L. Auslander, T. A. Brown, and J. W. Youngs , The imbedding of graphs in manifolds , Journal of Mathematics and Mechanics, 12 (1963), pp. 629--634. http://www.jstor.org/stable/24900840 http://www.jstor.org/stable/24900840

    arXiv 1963

  2. [2]

    Awerbuch, A

    B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin , Network decomposition and locality in distributed computation , in 30th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, May 1989, pp. 364--369. doi : http://doi.org/10.1109/SFCS.1989.63504 10.1109/SFCS.1989.63504

    arXiv 1989

  3. [3]

    S. A. Amiri, S. Schmid, and S. Siebertz , Distributed dominating set approximations beyond planar graphs , ACM Transactions on Algorithms, 15 (2019), pp. Article No. 39, pp. 1--18. doi : http://doi.org/10.1145/3093239 10.1145/3093239

    doi:10.1145/3093239 2019

  4. [4]

    Bonamy, N

    M. Bonamy, N. Bousquet, L. Esperet, C. Groenland, C.-H. Liu, F. Pirot, and A. Scott , Asymptotic dimension of minor-closed families and Assouad -- Nagata dimension of surfaces , Journal of the European Mathematical Society, 26 (2024), pp. 3739--3791. doi : http://doi.org/10.4171/JEMS/1341 10.4171/JEMS/1341

    doi:10.4171/jems/1341 2024

  5. [5]

    Bonamy, C

    M. Bonamy, C. Gavoille, T. Picavet, and A. Wesolek , Local constant approximation for dominating set on graphs excluding large minors , in 44th Annual ACM Symposium on Principles of Distributed Computing (PODC), ACM Press, June 2025. doi : http://doi.org/10.1145/3732772.3733531 10.1145/3732772.3733531

    arXiv 2025

  6. [6]

    Czygrinow, M

    A. Czygrinow, M. Ha \'n \'c kowiak, and W. Wawrzyniak , Fast distributed approximations in planar graphs , in 22nd International Symposium on Distributed Computing (DISC), vol. 5218 of Lecture Notes in Computer Science, Springer, September 2008, pp. 78--92. doi : http://doi.org/10.1007/978-3-540-87779-0_6 10.1007/978-3-540-87779-0_6

    doi:10.1007/978-3-540-87779-0_6 2008

  7. [7]

    Czygrinow, M

    A. Czygrinow, M. Ha \'n \'c kowiak, and W. Wawrzyniak , Distributed approximation algorithms for the minimum dominating set in K _h -minor-free graphs , in 29th International Symposium on Algorithms and Computation (ISAAC), vol. 123 of LIPIcs, December 2018, pp. 22:1--22:12. doi : http://doi.org/10.4230/LIPIcs.ISAAC.2018.22 10.4230/LIPIcs.ISAAC.2018.22

    doi:10.4230/lipics.isaac.2018.22 2018

  8. [8]

    Czygrinow, M

    A. Czygrinow, M. Ha \'n \'c kowiak, W. Wawrzyniak, and M. Witkowski , Distributed CONGEST _ BC constant approximation of MDS in bounded genus graphs , Theoretical Computer Science, 757 (2019), pp. 1--10. doi : http://doi.org/10.1016/j.tcs.2018.07.008 10.1016/j.tcs.2018.07.008

    doi:10.1016/j.tcs.2018.07.008 2019

Show all 28 references
  1. [9]

    Coupette and C

    C. Coupette and C. Lenzen , A breezing proof of the KMW bound , Tech. Rep. http://arxiv.org/abs/1504.07019v1 2002.06005v4 [cs.DC] , arXiv, October 2020

    2002 arXiv

  2. [10]

    Courcelle , The monadic second-order logic of graphs

    B. Courcelle , The monadic second-order logic of graphs. I . R ecognizable sets of finite graphs , Information and Computation, 85 (1990), pp. 12--75. doi : http://doi.org/10.1016/0890-5401(90)90043-H 10.1016/0890-5401(90)90043-H

    1990 doi

  3. [11]

    M. R. Garey and D. S. Johnson , Computers and Intractability - A Guide to the Theory of NP -Completeness , W.H. Freeman, 1979

    1979

  4. [12]

    Ghaffari, F

    M. Ghaffari, F. Kuhn, and Y. Maus , On the complexity of local distributed graph problems , in 49th Annual ACM Symposium on Theory of Computing (STOC), ACM Press, June 2017, pp. 784--797. doi : http://doi.org/10.1145/3055399.3055471 10.1145/3055399.3055471

    2017

  5. [13]

    Heydt, S

    O. Heydt, S. Kublenz, P. Ossona de Mendez, S. Siebertz, and A. Vigny , Distributed domination on sparse graph classes , European Journal of Combinatorics, 123 (2025), p. 103773. doi : http://doi.org/10.1016/j.ejc.2023.103773 10.1016/j.ejc.2023.103773

    2025

  6. [14]

    F. Kuhn, T. Moscibroda, and R. Wattenhofer , Local computation: Lower and upper bounds , Journal of the ACM, 63 (2016), pp. Article No. 17, pp. 1--44. doi : http://doi.org/10.1145/2742012 10.1145/2742012

    2016 doi

  7. [15]

    Kublenz, S

    S. Kublenz, S. Siebertz, and A. Vigny , Constant round distributed domination on graph classes with bounded expansion , in 28th International Colloquium on Structural Information & Communication Complexity (SIROCCO), T. Jurdzi \'n ski and S. Schmid, eds., vol. 12810 of Lecture...

    2021 doi

  8. [16]

    Kuhn and R

    F. Kuhn and R. Wattenhofer , Constant-time distributed dominating set approximation , Distributed Computing, 17 (2005), pp. 303--310. doi : http://doi.org/10.1007/s00446-004-0112-5 10.1007/s00446-004-0112-5

    2005 doi

  9. [17]

    Kikuno, N

    T. Kikuno, N. Yoshida, and Y. Kakuda , The NP -completeness of the dominating set problem in cubic planar graphs , IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E63-E (1980), pp. 443--444

    1980

  10. [18]

    N. Linial , Distributive graph algorithms -- G lobal solutions from local data , in 28th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society Press, October 1987, pp. 331--335. doi : http://doi.org/10.1109/SFCS.1987.20 10.1109/SFCS.1987.20

    1987 doi

  11. [19]

    Lenzen, Y

    C. Lenzen, Y. A. Oswald, and R. Wattenhofer , What can be approximated locally? -- C ase study: Dominating sets in planar graphs , in 20th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), ACM Press, June 2008, pp. 46--54. doi : http://doi.org/10.1145/13785...

    2008

  12. [20]

    Lenzen, Y.-A

    C. Lenzen, Y.-A. Pignolet, and R. Wattenhofer , Distributed minimum dominating set approximations in restricted families of graphs , Distributed Computing, 26 (2013), pp. 119--137. doi : http://doi.org/10.1007/s00446-013-0186-z 10.1007/s00446-013-0186-z

    2013 doi

  13. [21]

    Lenzen and R

    C. Lenzen and R. Wattenhofer , Leveraging Linial 's locality limit , in 22nd International Symposium on Distributed Computing (DISC), vol. 5218 of Lecture Notes in Computer Science, Springer, September 2008, pp. 394--407. doi : http://doi.org/10.1007/978-3-540-87779-0_27 10.10...

    2008 doi

  14. [22]

    Mohar and C

    B. Mohar and C. Thomassen , Graphs on Surfaces , The Johns Hopkins University Press, 2001

    2001

  15. [23]

    Rozho n and M

    V. Rozho n and M. Ghaffari , Polylogarithmic-time deterministic network decomposition and distributed derandomization , in 52nd Annual ACM Symposium on Theory of Computing (STOC), ACM Press, June 2020, pp. 350--363. doi : http://doi.org/10.1145/3357713.3384298 10.1145/3357713.3384298

    2020

  16. [24]

    Suomela , Survey of local algorithms , ACM Computing Surveys, 45 (2013), pp

    J. Suomela , Survey of local algorithms , ACM Computing Surveys, 45 (2013), pp. Article No. 24, pp. 1--40. doi : http://doi.org/10.1145/2431211.2431223 10.1145/2431211.2431223

    2013

  17. [25]

    von Rickenbach, R

    P. von Rickenbach, R. Wattenhofer, and A. Zollinger , Algorithmic models of interference in wireless ad hoc and sensor networks , IEEE/ACM Transactions on Networking, 17 (2009), pp. 172--185. doi : http://doi.org/10.1109/TNET.2008.926506 10.1109/TNET.2008.926506

    2009

  18. [26]

    P.-J. Wan, K. M. Alzoubi, and O. Frieder , Distributed construction of connected dominating set in wireless ad hoc networks , in 21st Annual Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), vol. 3, June 2002, pp. 1597--1604. doi : http://doi...

    2002 arXiv

  19. [27]

    Wan and C.-w

    P.-j. Wan and C.-w. Yi , On the longest edge of gabriel graphs in wireless ad hoc networks , IEEE Transactions on Parallel and Distributed Systems, 18 (2007), pp. 111--125. doi : http://doi.org/10.1109/TPDS.2007.253285 10.1109/TPDS.2007.253285

    2007

  20. [28]

    write newline

    " write newline "" before.all 'output.state := FUNCTION output.doi doi empty 'skip " doi : http://doi.org/" doi * " " * doi * " " * output if FUNCTION output.url url empty 'skip " " url * " " * url * " " * output if FUNCTION output.isbn isbn empty 'skip " isbn : " isbn * outpu...

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.