Search Results

Documents authored by Le, Hung

Document
DOI: 10.4230/LIPIcs.SoCG.2024.37
Optimal Euclidean Tree Covers

Authors: Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenković, Shay Solomon, and Cuong Than

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
A (1+e)-stretch tree cover of a metric space is a collection of trees, where every pair of points has a (1+e)-stretch path in one of the trees. The celebrated Dumbbell Theorem [Arya et al. STOC'95] states that any set of n points in d-dimensional Euclidean space admits a (1+e)-stretch tree cover with O_d(e^{-d} ⋅ log(1/e)) trees, where the O_d notation suppresses terms that depend solely on the dimension d. The running time of their construction is O_d(n log n ⋅ log(1/e)/e^d + n ⋅ e^{-2d}). Since the same point may occur in multiple levels of the tree, the maximum degree of a point in the tree cover may be as large as Ω(log Φ), where Φ is the aspect ratio of the input point set. In this work we present a (1+e)-stretch tree cover with O_d(e^{-d+1} ⋅ log(1/e)) trees, which is optimal (up to the log(1/e) factor). Moreover, the maximum degree of points in any tree is an absolute constant for any d. As a direct corollary, we obtain an optimal {routing scheme} in low-dimensional Euclidean spaces. We also present a (1+e)-stretch Steiner tree cover (that may use Steiner points) with O_d(e^{(-d+1)/2} ⋅ log(1/e)) trees, which too is optimal. The running time of our two constructions is linear in the number of edges in the respective tree covers, ignoring an additive O_d(n log n) term; this improves over the running time underlying the Dumbbell Theorem.
Cite as

Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenković, Shay Solomon, and Cuong Than. Optimal Euclidean Tree Covers. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.SoCG.2024.37,
  author =	{Chang, Hsien-Chih and Conroy, Jonathan and Le, Hung and Milenkovi\'{c}, Lazar and Solomon, Shay and Than, Cuong},
  title =	{{Optimal Euclidean Tree Covers}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{37:1--37:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.37},
  URN =		{urn:nbn:de:0030-drops-199828},
  doi =		{10.4230/LIPIcs.SoCG.2024.37},
  annote =	{Keywords: Tree cover, spanner, Steiner point, routing, bounded-degree, quadtree, net-tree}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.38
Computing Diameter+2 in Truly-Subquadratic Time for Unit-Disk Graphs

Authors: Hsien-Chih Chang, Jie Gao, and Hung Le

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
Finding the diameter of a graph in general cannot be done in truly subquadratic assuming the Strong Exponential Time Hypothesis (SETH), even when the underlying graph is unweighted and sparse. When restricting to concrete classes of graphs and assuming SETH, planar graphs and minor-free graphs admit truly subquadratic algorithms, while geometric intersection graphs of unit balls, congruent equilateral triangles, and unit segments do not. Unit-disk graphs is one of the major open cases where the complexity of diameter computation remains unknown. More generally, it is conjectured that a truly subquadratic time algorithm exists for pseudo-disk graphs where each pair of objects has at most two intersections on the boundary. In this paper, we show a truly-subquadratic algorithm of running time O^~(n^{2-1/18}), for finding the diameter in a unit-disk graph, whose output differs from the optimal solution by at most 2. This is the first algorithm that provides an additive guarantee in distortion, independent of the size or the diameter of the graph. Our algorithm requires two important technical elements. First, we show that for the intersection graph of pseudo-disks, the graph VC-dimension - either of k-hop balls or the distance encoding vectors - is 4. This contrasts to the VC dimension of the pseudo-disks themselves as geometric ranges (which is known to be 3). Second, we introduce a clique-based r-clustering for geometric intersection graphs, which is an analog of the r-division construction for planar graphs. We also showcase the new techniques by establishing new results for distance oracles for unit-disk graphs with subquadratic storage and O(1) query time. The results naturally extend to unit L₁ or L_∞-disks and fat pseudo-disks of similar size. Last, if the pseudo-disks additionally have bounded ply, we have a truly subquadratic algorithm to find the exact diameter.
Cite as

Hsien-Chih Chang, Jie Gao, and Hung Le. Computing Diameter+2 in Truly-Subquadratic Time for Unit-Disk Graphs. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.SoCG.2024.38,
  author =	{Chang, Hsien-Chih and Gao, Jie and Le, Hung},
  title =	{{Computing Diameter+2 in Truly-Subquadratic Time for Unit-Disk Graphs}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.38},
  URN =		{urn:nbn:de:0030-drops-199833},
  doi =		{10.4230/LIPIcs.SoCG.2024.38},
  annote =	{Keywords: Unit-disk graph, pseudo-disks, r-division, VC-dimension, distance oracle, clique-based separator}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.47
Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave Inverse-Ackermann Function

Authors: Hung Le, Lazar Milenković, and Shay Solomon

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
In STOC'95 [S. Arya et al., 1995] Arya et al. showed that any set of n points in ℝ^d admits a (1+ε)-spanner with hop-diameter at most 2 (respectively, 3) and O(n log n) edges (resp., O(n log log n) edges). They also gave a general upper bound tradeoff of hop-diameter k with O(n α_k(n)) edges, for any k ≥ 2. The function α_k is the inverse of a certain Ackermann-style function, where α₀(n) = ⌈n/2⌉, α₁(n) = ⌈√n⌉, α₂(n) = ⌈log n⌉, α₃(n) = ⌈log log n⌉, α₄(n) = log^* n, α₅(n) = ⌊ 1/2 log^*n ⌋, …. Roughly speaking, for k ≥ 2 the function α_{k} is close to ⌊(k-2)/2⌋-iterated log-star function, i.e., log with ⌊(k-2)/2⌋ stars. Despite a large body of work on spanners of bounded hop-diameter, the fundamental question of whether this tradeoff between size and hop-diameter of Euclidean (1+ε)-spanners is optimal has remained open, even in one-dimensional spaces. Three lower bound tradeoffs are known: - An optimal k versus Ω(n α_k(n)) by Alon and Schieber [N. Alon and B. Schieber, 1987], but it applies to stretch 1 (not 1+ε). - A suboptimal k versus Ω(nα_{2k+6}(n)) by Chan and Gupta [H. T.-H. Chan and A. Gupta, 2006]. - A suboptimal k versus Ω(n/(2^{6⌊k/2⌋}) α_k(n)) by Le et al. [Le et al., 2022]. This paper establishes the optimal k versus Ω(n α_k(n)) lower bound tradeoff for stretch 1+ε, for any ε > 0, and for any k. An important conceptual contribution of this work is in achieving optimality by shaving off an extremely slowly growing term, namely 2^{6⌊k/2⌋} for k ≤ O(α(n)); such a fine-grained optimization (that achieves optimality) is very rare in the literature. To shave off the 2^{6⌊k/2⌋} term from the previous bound of Le et al., our argument has to drill much deeper. In particular, we propose a new way of analyzing recurrences that involve inverse-Ackermann style functions, and our key technical contribution is in presenting the first explicit construction of concave versions of these functions. An important advantage of our approach over previous ones is its robustness: While all previous lower bounds are applicable only to restricted 1-dimensional point sets, ours applies even to random point sets in constant-dimensional spaces.
Cite as

Hung Le, Lazar Milenković, and Shay Solomon. Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave Inverse-Ackermann Function. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{le_et_al:LIPIcs.SoCG.2023.47,
  author =	{Le, Hung and Milenkovi\'{c}, Lazar and Solomon, Shay},
  title =	{{Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave Inverse-Ackermann Function}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{47:1--47:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.47},
  URN =		{urn:nbn:de:0030-drops-178976},
  doi =		{10.4230/LIPIcs.SoCG.2023.47},
  annote =	{Keywords: Euclidean spanners, Ackermann functions, convex functions, hop-diameter}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.54
Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound

Authors: Hung Le, Lazar Milenković, and Shay Solomon

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
In STOC'95 [ADMSS95] Arya et al. showed that any set of n points in R^d admits a (1+ε)-spanner with hop-diameter at most 2 (respectively, 3) and O(n log n) edges (resp., O(n log log n) edges). They also gave a general upper bound tradeoff of hop-diameter at most k and O(n α_k(n)) edges, for any k≥2. The function α_k is the inverse of a certain Ackermann-style function at the ⌊k/2⌋th level of the primitive recursive hierarchy, where α₀(n)=⌈n/2⌉, α₁(n)=⌈√n⌉, α₂(n)=⌈log n⌉, α₃(n)=⌈log log n⌉, α₄(n)=log^* n, α₅(n)=⌊1/2 log^*n⌋, .... Roughly speaking, for k≥2 the function α_{k} is close to ⌊(k-2)/2⌋-iterated log-star function, i.e., log with ⌊(k-2)/2⌋ stars. Also, α_{2α(n)+4}(n)≤4, where α(n) is the one-parameter inverse Ackermann function, which is an extremely slowly growing function. Whether or not this tradeoff is tight has remained open, even for the cases k=2 and k=3. Two lower bounds are known: The first applies only to spanners with stretch 1 and the second is sub-optimal and applies only to sufficiently large (constant) values of k. In this paper we prove a tight lower bound for any constant k: For any fixed ε>0, any (1+ε)-spanner for the uniform line metric with hop-diameter at most k must have at least Ω(n α_k(n)) edges.
Cite as

Hung Le, Lazar Milenković, and Shay Solomon. Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 54:1-54:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{le_et_al:LIPIcs.SoCG.2022.54,
  author =	{Le, Hung and Milenkovi\'{c}, Lazar and Solomon, Shay},
  title =	{{Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{54:1--54:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.54},
  URN =		{urn:nbn:de:0030-drops-160629},
  doi =		{10.4230/LIPIcs.SoCG.2022.54},
  annote =	{Keywords: Euclidean spanners, hop-diameter, inverse-Ackermann, lower bounds, sparse spanners}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.96
Dynamic Matching Algorithms Under Vertex Updates

Authors: Hung Le, Lazar Milenković, Shay Solomon, and Virginia Vassilevska Williams

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
Dynamic graph matching algorithms have been extensively studied, but mostly under edge updates. This paper concerns dynamic matching algorithms under vertex updates, where in each update step a single vertex is either inserted or deleted along with its incident edges. A basic setting arising in online algorithms and studied by Bosek et al. [FOCS'14] and Bernstein et al. [SODA'18] is that of dynamic approximate maximum cardinality matching (MCM) in bipartite graphs in which one side is fixed and vertices on the other side either arrive or depart via vertex updates. In the BASIC-incremental setting, vertices only arrive, while in the BASIC-decremental setting vertices only depart. When vertices can both arrive and depart, we have the BASIC-dynamic setting. In this paper we also consider the setting in which both sides of the bipartite graph are dynamic. We call this the MEDIUM-dynamic setting, and MEDIUM-decremental is the restriction when vertices can only depart. The GENERAL-dynamic setting is when the graph is not necessarily bipartite and the vertices can both depart and arrive. Denote by K the total number of edges inserted and deleted to and from the graph throughout the entire update sequence. A well-studied measure, the recourse of a dynamic matching algorithm is the number of changes made to the matching per step. We largely focus on Maximal Matching (MM) which is a 2-approximation to the MCM. Our main results are as follows. - In the BASIC-dynamic setting, there is a straightforward algorithm for maintaining a MM, with a total runtime of O(K) and constant worst-case recourse. In fact, this algorithm never removes an edge from the matching; we refer to such an algorithm as irrevocable. - For the MEDIUM-dynamic setting we give a strong conditional lower bound that even holds in the MEDIUM-decremental setting: if for any fixed η > 0, there is an irrevocable decremental MM algorithm with a total runtime of O(K ⋅ n^{1-η}), this would refute the OMv conjecture; a similar (but weaker) hardness result can be achieved via a reduction from the Triangle Detection conjecture. - Next, we consider the GENERAL-dynamic setting, and design an MM algorithm with a total runtime of O(K) and constant worst-case recourse. We achieve this result via a 1-revocable algorithm, which may remove just one edge per update step. As argued above, an irrevocable algorithm with such a runtime is not likely to exist. - Finally, back to the BASIC-dynamic setting, we present an algorithm with a total runtime of O(K), which provides an (e/(e-1))-approximation to the MCM. To this end, we build on the classic "ranking" online algorithm by Karp et al. [STOC'90]. Beyond the results, our work draws connections between the areas of dynamic graph algorithms and online algorithms, and it proposes several open questions that seem to be overlooked thus far.
Cite as

Hung Le, Lazar Milenković, Shay Solomon, and Virginia Vassilevska Williams. Dynamic Matching Algorithms Under Vertex Updates. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 96:1-96:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{le_et_al:LIPIcs.ITCS.2022.96,
  author =	{Le, Hung and Milenkovi\'{c}, Lazar and Solomon, Shay and Vassilevska Williams, Virginia},
  title =	{{Dynamic Matching Algorithms Under Vertex Updates}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{96:1--96:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.96},
  URN =		{urn:nbn:de:0030-drops-156923},
  doi =		{10.4230/LIPIcs.ITCS.2022.96},
  annote =	{Keywords: maximal matching, approximate matching, dynamic algorithm, vertex updates}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.67
Light Euclidean Spanners with Steiner Points

Authors: Hung Le and Shay Solomon

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
The FOCS'19 paper of Le and Solomon [Hung Le and Shay Solomon, 2019], culminating a long line of research on Euclidean spanners, proves that the lightness (normalized weight) of the greedy (1+ε)-spanner in ℝ^d is Õ(ε^{-d}) for any d = O(1) and any ε = Ω(n^{-1/(d-1)}) (where Õ hides polylogarithmic factors of 1/ε), and also shows the existence of point sets in ℝ^d for which any (1+ε)-spanner must have lightness Ω(ε^{-d}). Given this tight bound on the lightness, a natural arising question is whether a better lightness bound can be achieved using Steiner points. Our first result is a construction of Steiner spanners in ℝ² with lightness O(ε^{-1} log Δ), where Δ is the spread of the point set. In the regime of Δ ≪ 2^(1/ε), this provides an improvement over the lightness bound of [Hung Le and Shay Solomon, 2019]; this regime of parameters is of practical interest, as point sets arising in real-life applications (e.g., for various random distributions) have polynomially bounded spread, while in spanner applications ε often controls the precision, and it sometimes needs to be much smaller than O(1/log n). Moreover, for spread polynomially bounded in 1/ε, this upper bound provides a quadratic improvement over the non-Steiner bound of [Hung Le and Shay Solomon, 2019], We then demonstrate that such a light spanner can be constructed in O_ε(n) time for polynomially bounded spread, where O_ε hides a factor of poly(1/(ε)). Finally, we extend the construction to higher dimensions, proving a lightness upper bound of Õ(ε^{-(d+1)/2} + ε^{-2} log Δ) for any 3 ≤ d = O(1) and any ε = Ω(n^{-1/(d-1)}).
Cite as

Hung Le and Shay Solomon. Light Euclidean Spanners with Steiner Points. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 67:1-67:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{le_et_al:LIPIcs.ESA.2020.67,
  author =	{Le, Hung and Solomon, Shay},
  title =	{{Light Euclidean Spanners with Steiner Points}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{67:1--67:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.67},
  URN =		{urn:nbn:de:0030-drops-129331},
  doi =		{10.4230/LIPIcs.ESA.2020.67},
  annote =	{Keywords: Euclidean spanners, Steiner spanners, light spanners}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2016.8
Optimal Dynamic Program for r-Domination Problems over Tree Decompositions

Authors: Glencora Borradaile and Hung Le

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

Abstract
There has been recent progress in showing that the exponential dependence on treewidth in dynamic programming algorithms for solving NP-hard problems is optimal under the Strong Exponential Time Hypothesis (SETH). We extend this work to r-domination problems. In r-dominating set, one wishes to find a minimum subset S of vertices such that every vertex of G is within r hops of some vertex in S. In connected r-dominating set, one additionally requires that the set induces a connected subgraph of G. We give a O((2r+1)^tw n) time algorithm for r-dominating set and a randomized O((2r+2)^tw n^{O(1)}) time algorithm for connected r-dominating set in n-vertex graphs of treewidth tw. We show that the running time dependence on r and tw is the best possible under SETH. This adds to earlier observations that a "+1" in the denominator is required for connectivity constraints.
Cite as

Glencora Borradaile and Hung Le. Optimal Dynamic Program for r-Domination Problems over Tree Decompositions. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{borradaile_et_al:LIPIcs.IPEC.2016.8,
  author =	{Borradaile, Glencora and Le, Hung},
  title =	{{Optimal Dynamic Program for r-Domination Problems over Tree Decompositions}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{8:1--8:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.8},
  URN =		{urn:nbn:de:0030-drops-69199},
  doi =		{10.4230/LIPIcs.IPEC.2016.8},
  annote =	{Keywords: r-dominating set, Exponential Time Hypothesis, Dynamic Programming}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact