Search Results

Documents authored by Borradaile, Glencora

Document
DOI: 10.4230/LIPIcs.SWAT.2020.15
Low-Stretch Spanning Trees of Graphs with Bounded Width

Authors: Glencora Borradaile, Erin Wolf Chambers, David Eppstein, William Maxwell, and Amir Nayyeri

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
We study the problem of low-stretch spanning trees in graphs of bounded width: bandwidth, cutwidth, and treewidth. We show that any simple connected graph G with a linear arrangement of bandwidth b can be embedded into a distribution T of spanning trees such that the expected stretch of each edge of G is O(b²). Our proof implies a linear time algorithm for sampling from T. Therefore, we have a linear time algorithm that finds a spanning tree of G with average stretch O(b²) with high probability. We also describe a deterministic linear-time algorithm for computing a spanning tree of G with average stretch O(b³). For graphs of cutwidth c, we construct a spanning tree with stretch O(c²) in linear time. Finally, when G has treewidth k we provide a dynamic programming algorithm computing a minimum stretch spanning tree of G that runs in polynomial time with respect to the number of vertices of G.
Cite as

Glencora Borradaile, Erin Wolf Chambers, David Eppstein, William Maxwell, and Amir Nayyeri. Low-Stretch Spanning Trees of Graphs with Bounded Width. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{borradaile_et_al:LIPIcs.SWAT.2020.15,
  author =	{Borradaile, Glencora and Chambers, Erin Wolf and Eppstein, David and Maxwell, William and Nayyeri, Amir},
  title =	{{Low-Stretch Spanning Trees of Graphs with Bounded Width}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{15:1--15:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.15},
  URN =		{urn:nbn:de:0030-drops-122622},
  doi =		{10.4230/LIPIcs.SWAT.2020.15},
  annote =	{Keywords: Treewidth, low-stretch spanning tree, fundamental cycle basis}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.21
Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes

Authors: Glencora Borradaile, William Maxwell, and Amir Nayyeri

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
We study two optimization problems on simplicial complexes with homology over ℤ₂, the minimum bounded chain problem: given a d-dimensional complex 𝒦 embedded in ℝ^(d+1) and a null-homologous (d-1)-cycle C in 𝒦, find the minimum d-chain with boundary C, and the minimum homologous chain problem: given a (d+1)-manifold ℳ and a d-chain D in ℳ, find the minimum d-chain homologous to D. We show strong hardness results for both problems even for small values of d; d = 2 for the former problem, and d=1 for the latter problem. We show that both problems are APX-hard, and hard to approximate within any constant factor assuming the unique games conjecture. On the positive side, we show that both problems are fixed-parameter tractable with respect to the size of the optimal solution. Moreover, we provide an O(√{log β_d})-approximation algorithm for the minimum bounded chain problem where β_d is the dth Betti number of 𝒦. Finally, we provide an O(√{log n_{d+1}})-approximation algorithm for the minimum homologous chain problem where n_{d+1} is the number of (d+1)-simplices in ℳ.
Cite as

Glencora Borradaile, William Maxwell, and Amir Nayyeri. Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{borradaile_et_al:LIPIcs.SoCG.2020.21,
  author =	{Borradaile, Glencora and Maxwell, William and Nayyeri, Amir},
  title =	{{Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.21},
  URN =		{urn:nbn:de:0030-drops-121799},
  doi =		{10.4230/LIPIcs.SoCG.2020.21},
  annote =	{Keywords: computational topology, algorithmic complexity, simplicial complexes}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.3
A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs

Authors: Glencora Borradaile and Baigong Zheng

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
We consider the problem of finding the minimum-weight subgraph that satisfies given connectivity requirements. Specifically, given a requirement r in {0, 1, 2, 3} for every vertex, we seek the minimum-weight subgraph that contains, for every pair of vertices u and v, at least min{r(v), r(u)} edge-disjoint u-to-v paths. We give a polynomial-time approximation scheme (PTAS) for this problem when the input graph is planar and the subgraph may use multiple copies of any given edge (paying for each edge separately). This generalizes an earlier result for r in {0, 1, 2}. In order to achieve this PTAS, we prove some properties of triconnected planar graphs that may be of independent interest.
Cite as

Glencora Borradaile and Baigong Zheng. A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 3:1-3:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{borradaile_et_al:LIPIcs.APPROX-RANDOM.2017.3,
  author =	{Borradaile, Glencora and Zheng, Baigong},
  title =	{{A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{3:1--3:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.3},
  URN =		{urn:nbn:de:0030-drops-75525},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.3},
  annote =	{Keywords: Three-Edge Connectivity, Polynomial-Time Approximation Schemes, Planar Graphs}
}
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}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.22
All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs

Authors: Glencora Borradaile, David Eppstein, Amir Nayyeri, and Christian Wulff-Nilsen

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
For an undirected n-vertex graph G with non-negative edge-weights, we consider the following type of query: given two vertices s and t in G, what is the weight of a minimum st-cut in G? We solve this problem in preprocessing time O(n log^3 n) for graphs of bounded genus, giving the first sub-quadratic time algorithm for this class of graphs. Our result also improves by a logarithmic factor a previous algorithm by Borradaile, Sankowski and Wulff-Nilsen (FOCS 2010) that applied only to planar graphs. Our algorithm constructs a Gomory-Hu tree for the given graph, providing a data structure with space O(n) that can answer minimum-cut queries in constant time. The dependence on the genus of the input graph in our preprocessing time is 2^{O(g^2)}.
Cite as

Glencora Borradaile, David Eppstein, Amir Nayyeri, and Christian Wulff-Nilsen. All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{borradaile_et_al:LIPIcs.SoCG.2016.22,
  author =	{Borradaile, Glencora and Eppstein, David and Nayyeri, Amir and Wulff-Nilsen, Christian},
  title =	{{All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.22},
  URN =		{urn:nbn:de:0030-drops-59149},
  doi =		{10.4230/LIPIcs.SoCG.2016.22},
  annote =	{Keywords: minimum cuts, surface-embedded graphs, Gomory-Hu tree}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.23
Minimum Cycle and Homology Bases of Surface Embedded Graphs

Authors: Glencora Borradaile, Erin Wolf Chambers, Kyle Fox, and Amir Nayyeri

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We study the problems of finding a minimum cycle basis (a minimum weight set of cycles that form a basis for the cycle space) and a minimum homology basis (a minimum weight set of cycles that generates the 1-dimensional (Z_2)-homology classes) of an undirected graph embedded on an orientable surface of genus g. The problems are closely related, because the minimum cycle basis of a graph contains its minimum homology basis, and the minimum homology basis of the 1-skeleton of any graph is exactly its minimum cycle basis. For the minimum cycle basis problem, we give a deterministic O(n^omega + 2^2g n^2)-time algorithm. The best known existing algorithms for surface embedded graphs are those for general sparse graphs: an O(n^omega) time Monte Carlo algorithm [Amaldi et. al., ESA'09] and a deterministic O(n^3) time algorithm [Mehlhorn and Michail, TALG'09]. For the minimum homology basis problem, we give an O(g^3 n log n)-time algorithm, improving on existing algorithms for many values of g and n.
Cite as

Glencora Borradaile, Erin Wolf Chambers, Kyle Fox, and Amir Nayyeri. Minimum Cycle and Homology Bases of Surface Embedded Graphs. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{borradaile_et_al:LIPIcs.SoCG.2016.23,
  author =	{Borradaile, Glencora and Chambers, Erin Wolf and Fox, Kyle and Nayyeri, Amir},
  title =	{{Minimum Cycle and Homology Bases of Surface Embedded Graphs}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.23},
  URN =		{urn:nbn:de:0030-drops-59152},
  doi =		{10.4230/LIPIcs.SoCG.2016.23},
  annote =	{Keywords: Cycle basis, Homology basis, Topological graph theory}
}
Document
DOI: 10.4230/DagRep.3.10.36
Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 13421)

Authors: Glencora Borradaile, Philp Klein, Dániel Marx, and Claire Mathieu

Published in: Dagstuhl Reports, Volume 3, Issue 10 (2014)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13421 "Algorithms for Optimization Problems in Planar Graphs". The seminar was held from October 13 to October 18, 2013. This report contains abstracts for the recent developments in planar graph algorithms discussed during the seminar as well as summaries of open problems in this area of research.
Cite as

Glencora Borradaile, Philp Klein, Dániel Marx, and Claire Mathieu. Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 13421). In Dagstuhl Reports, Volume 3, Issue 10, pp. 36-57, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{borradaile_et_al:DagRep.3.10.36,
  author =	{Borradaile, Glencora and Klein, Philp and Marx, D\'{a}niel and Mathieu, Claire},
  title =	{{Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 13421)}},
  pages =	{36--57},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{3},
  number =	{10},
  editor =	{Borradaile, Glencora and Klein, Philp and Marx, D\'{a}niel and Mathieu, Claire},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.10.36},
  URN =		{urn:nbn:de:0030-drops-44274},
  doi =		{10.4230/DagRep.3.10.36},
  annote =	{Keywords: Algorithms, planar graphs, theory, approximation, fixed-parameter tractable, network flow, network design, kernelization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1835
Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs

Authors: Glencora Borradaile, Erik D. Demaine, and Siamak Tazari

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
We present the first polynomial-time approximation schemes (PTASes) for the following subset-connectivity problems in edge-weighted graphs of bounded genus: Steiner tree, low-connectivity survivable-network design, and subset TSP. The schemes run in $O(n \log n)$ time for graphs embedded on both orientable and non-orientable surfaces. This work generalizes the PTAS frameworks of Borradaile, Klein, and Mathieu (2007 and 2006) from planar graphs to bounded-genus graphs: any future problems shown to admit the required structure theorem for planar graphs will similarly extend to bounded-genus graphs.
Cite as

Glencora Borradaile, Erik D. Demaine, and Siamak Tazari. Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 171-182, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{borradaile_et_al:LIPIcs.STACS.2009.1835,
  author =	{Borradaile, Glencora and Demaine, Erik D. and Tazari, Siamak},
  title =	{{Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{171--182},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1835},
  URN =		{urn:nbn:de:0030-drops-18355},
  doi =		{10.4230/LIPIcs.STACS.2009.1835},
  annote =	{Keywords: Polynomial-time approximation scheme, Bounded-genus graph, Embedded graph, Steiner tree, Survivable-network design, Subset TSP}
}
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 About DROPS Imprint Privacy Contact