Search Results

Documents authored by Fox, Kyle

Document
DOI: 10.4230/LIPIcs.ISAAC.2022.10
Clustering with Faulty Centers

Authors: Kyle Fox, Hongyao Huang, and Benjamin Raichel

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
In this paper we introduce and formally study the problem of k-clustering with faulty centers. Specifically, we study the faulty versions of k-center, k-median, and k-means clustering, where centers have some probability of not existing, as opposed to prior work where clients had some probability of not existing. For all three problems we provide fixed parameter tractable algorithms, in the parameters k, d, and ε, that (1+ε)-approximate the minimum expected cost solutions for points in d dimensional Euclidean space. For Faulty k-center we additionally provide a 5-approximation for general metrics. Significantly, all of our algorithms have a small dependence on n. Specifically, our Faulty k-center algorithms have only linear dependence on n, while for our algorithms for Faulty k-median and Faulty k-means the dependence is still only n^(1 + o(1)).
Cite as

Kyle Fox, Hongyao Huang, and Benjamin Raichel. Clustering with Faulty Centers. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.ISAAC.2022.10,
  author =	{Fox, Kyle and Huang, Hongyao and Raichel, Benjamin},
  title =	{{Clustering with Faulty Centers}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.10},
  URN =		{urn:nbn:de:0030-drops-172950},
  doi =		{10.4230/LIPIcs.ISAAC.2022.10},
  annote =	{Keywords: clustering, approximation, probabilistic input, uncertain input}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.13
Computation of Cycle Bases in Surface Embedded Graphs

Authors: Kyle Fox and Thomas Stanley

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We present an O(n³ g²log g + m) + Õ(n^{ω + 1}) time deterministic algorithm to find the minimum cycle basis of a directed graph embedded on an orientable surface of genus g. This result improves upon the previous fastest known running time of O(m³n + m²n² log n) applicable to general directed graphs. While an O(n^ω + 2^{2g}n² + m) time deterministic algorithm was known for undirected graphs, the use of the underlying field ℚ in the directed case (as opposed to ℤ₂ for the undirected case) presents extra challenges. It turns out that some of our new observations are useful for both variants of the problem, so we present an O(n^ω + n² g² log g + m) time deterministic algorithm for undirected graphs as well.
Cite as

Kyle Fox and Thomas Stanley. Computation of Cycle Bases in Surface Embedded Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.ISAAC.2022.13,
  author =	{Fox, Kyle and Stanley, Thomas},
  title =	{{Computation of Cycle Bases in Surface Embedded Graphs}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.13},
  URN =		{urn:nbn:de:0030-drops-172982},
  doi =		{10.4230/LIPIcs.ISAAC.2022.13},
  annote =	{Keywords: cycle basis, surface embedded graphs, homology}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.72
A Faster Algorithm for Maximum Flow in Directed Planar Graphs with Vertex Capacities

Authors: Julian Enoch, Kyle Fox, Dor Mesica, and Shay Mozes

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We give an O(k³ Δ n log n min(k, log² n) log²(nC))-time algorithm for computing maximum integer flows in planar graphs with integer arc and vertex capacities bounded by C, and k sources and sinks. This improves by a factor of max(k²,k log² n) over the fastest algorithm previously known for this problem [Wang, SODA 2019]. The speedup is obtained by two independent ideas. First we replace an iterative procedure of Wang that uses O(k) invocations of an O(k³ n log³ n)-time algorithm for maximum flow algorithm in a planar graph with k apices [Borradaile et al., FOCS 2012, SICOMP 2017], by an alternative procedure that only makes one invocation of the algorithm of Borradaile et al. Second, we show two alternatives for computing flows in the k-apex graphs that arise in our modification of Wang’s procedure faster than the algorithm of Borradaile et al. In doing so, we introduce and analyze a sequential implementation of the parallel highest-distance push-relabel algorithm of Goldberg and Tarjan [JACM 1988].
Cite as

Julian Enoch, Kyle Fox, Dor Mesica, and Shay Mozes. A Faster Algorithm for Maximum Flow in Directed Planar Graphs with Vertex Capacities. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 72:1-72:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{enoch_et_al:LIPIcs.ISAAC.2021.72,
  author =	{Enoch, Julian and Fox, Kyle and Mesica, Dor and Mozes, Shay},
  title =	{{A Faster Algorithm for Maximum Flow in Directed Planar Graphs with Vertex Capacities}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{72:1--72:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.72},
  URN =		{urn:nbn:de:0030-drops-155057},
  doi =		{10.4230/LIPIcs.ISAAC.2021.72},
  annote =	{Keywords: flow, planar graphs, vertex capacities}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.26
Approximating the (Continuous) Fréchet Distance

Authors: Connor Colombe and Kyle Fox

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We describe the first strongly subquadratic time algorithm with subexponential approximation ratio for approximately computing the Fréchet distance between two polygonal chains. Specifically, let P and Q be two polygonal chains with n vertices in d-dimensional Euclidean space, and let α ∈ [√n, n]. Our algorithm deterministically finds an O(α)-approximate Fréchet correspondence in time O((n³ / α²) log n). In particular, we get an O(n)-approximation in near-linear O(n log n) time, a vast improvement over the previously best know result, a linear time 2^O(n)-approximation. As part of our algorithm, we also describe how to turn any approximate decision procedure for the Fréchet distance into an approximate optimization algorithm whose approximation ratio is the same up to arbitrarily small constant factors. The transformation into an approximate optimization algorithm increases the running time of the decision procedure by only an O(log n) factor.
Cite as

Connor Colombe and Kyle Fox. Approximating the (Continuous) Fréchet Distance. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{colombe_et_al:LIPIcs.SoCG.2021.26,
  author =	{Colombe, Connor and Fox, Kyle},
  title =	{{Approximating the (Continuous) Fr\'{e}chet Distance}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{26:1--26:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.26},
  URN =		{urn:nbn:de:0030-drops-138259},
  doi =		{10.4230/LIPIcs.SoCG.2021.26},
  annote =	{Keywords: Fr\'{e}chet distance, approximation algorithm, approximate decision procedure}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.45
A Near-Linear Time Approximation Scheme for Geometric Transportation with Arbitrary Supplies and Spread

Authors: Kyle Fox and Jiashuai Lu

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

Abstract
The geometric transportation problem takes as input a set of points P in d-dimensional Euclidean space and a supply function μ : P → ℝ. The goal is to find a transportation map, a non-negative assignment τ : P × P → ℝ_{≥ 0} to pairs of points, so the total assignment leaving each point is equal to its supply, i.e., ∑_{r ∈ P} τ(q, r) - ∑_{p ∈ P} τ(p, q) = μ(q) for all points q ∈ P. The goal is to minimize the weighted sum of Euclidean distances for the pairs, ∑_{(p, q) ∈ P × P} τ(p, q) ⋅ ||q - p||₂. We describe the first algorithm for this problem that returns, with high probability, a (1 + ε)-approximation to the optimal transportation map in O(n poly(1 / ε) polylog n) time. In contrast to the previous best algorithms for this problem, our near-linear running time bound is independent of the spread of P and the magnitude of its real-valued supplies.
Cite as

Kyle Fox and Jiashuai Lu. A Near-Linear Time Approximation Scheme for Geometric Transportation with Arbitrary Supplies and Spread. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 45:1-45:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.SoCG.2020.45,
  author =	{Fox, Kyle and Lu, Jiashuai},
  title =	{{A Near-Linear Time Approximation Scheme for Geometric Transportation with Arbitrary Supplies and Spread}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{45:1--45:18},
  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.45},
  URN =		{urn:nbn:de:0030-drops-122034},
  doi =		{10.4230/LIPIcs.SoCG.2020.45},
  annote =	{Keywords: Transportation map, earth mover’s distance, shape matching, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.23
Approximating the Geometric Edit Distance

Authors: Kyle Fox and Xinyi Li

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
Edit distance is a measurement of similarity between two sequences such as strings, point sequences, or polygonal curves. Many matching problems from a variety of areas, such as signal analysis, bioinformatics, etc., need to be solved in a geometric space. Therefore, the geometric edit distance (GED) has been studied. In this paper, we describe the first strictly sublinear approximate near-linear time algorithm for computing the GED of two point sequences in constant dimensional Euclidean space. Specifically, we present a randomized O(n log^2n) time O(sqrt n)-approximation algorithm. Then, we generalize our result to give a randomized alpha-approximation algorithm for any alpha in [1, sqrt n], running in time O~(n^2/alpha^2). Both algorithms are Monte Carlo and return approximately optimal solutions with high probability.
Cite as

Kyle Fox and Xinyi Li. Approximating the Geometric Edit Distance. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.ISAAC.2019.23,
  author =	{Fox, Kyle and Li, Xinyi},
  title =	{{Approximating the Geometric Edit Distance}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{23:1--23:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.23},
  URN =		{urn:nbn:de:0030-drops-115195},
  doi =		{10.4230/LIPIcs.ISAAC.2019.23},
  annote =	{Keywords: Geometric edit distance, Approximation, Randomized algorithms}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2017.8
Maintaining Reeb Graphs of Triangulated 2-Manifolds

Authors: Pankaj K. Agarwal, Kyle Fox, and Abhinandan Nath

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Abstract
Let M be a triangulated, orientable 2-manifold of genus g without boundary, and let h be a height function over M that is linear within each triangle. We present a kinetic data structure (KDS) for maintaining the Reeb graph R of h as the heights of M's vertices vary continuously with time. Assuming the heights of two vertices of M become equal only O(1) times, the KDS processes O((k + g) n \polylog n) events; n is the number of vertices in M, and k is the number of external events which change the combinatorial structure of R. Each event is processed in O(\log^2 n) time, and the total size of our KDS is O(gn). The KDS can be extended to maintain an augmented Reeb graph as well.
Cite as

Pankaj K. Agarwal, Kyle Fox, and Abhinandan Nath. Maintaining Reeb Graphs of Triangulated 2-Manifolds. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.FSTTCS.2017.8,
  author =	{Agarwal, Pankaj K. and Fox, Kyle and Nath, Abhinandan},
  title =	{{Maintaining Reeb Graphs of Triangulated 2-Manifolds}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.8},
  URN =		{urn:nbn:de:0030-drops-84043},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.8},
  annote =	{Keywords: Reeb graphs, 2-manifolds, topological graph theory}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.7
Faster Algorithms for the Geometric Transportation Problem

Authors: Pankaj K. Agarwal, Kyle Fox, Debmalya Panigrahi, Kasturi R. Varadarajan, and Allen Xiao

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Let R, B be a set of n points in R^d, for constant d, where the points of R have integer supplies, points of B have integer demands, and the sum of supply is equal to the sum of demand. Let d(.,.) be a suitable distance function such as the L_p distance. The transportation problem asks to find a map tau : R x B --> N such that sum_{b in B}tau(r,b) = supply(r), sum_{r in R}tau(r,b) = demand(b), and sum_{r in R, b in B} tau(r,b) d(r,b) is minimized. We present three new results for the transportation problem when d(.,.) is any L_p metric: * For any constant epsilon > 0, an O(n^{1+epsilon}) expected time randomized algorithm that returns a transportation map with expected cost O(log^2(1/epsilon)) times the optimal cost. * For any epsilon > 0, a (1+epsilon)-approximation in O(n^{3/2}epsilon^{-d}polylog(U)polylog(n)) time, where U is the maximum supply or demand of any point. * An exact strongly polynomial O(n^2 polylog n) time algorithm, for d = 2.
Cite as

Pankaj K. Agarwal, Kyle Fox, Debmalya Panigrahi, Kasturi R. Varadarajan, and Allen Xiao. Faster Algorithms for the Geometric Transportation Problem. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2017.7,
  author =	{Agarwal, Pankaj K. and Fox, Kyle and Panigrahi, Debmalya and Varadarajan, Kasturi R. and Xiao, Allen},
  title =	{{Faster Algorithms for the Geometric Transportation Problem}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.7},
  URN =		{urn:nbn:de:0030-drops-72344},
  doi =		{10.4230/LIPIcs.SoCG.2017.7},
  annote =	{Keywords: transportation map, earth mover's distance, shape matching, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.6
Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences

Authors: Pankaj K. Agarwal, Kyle Fox, Jiangwei Pan, and Rex Ying

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

Abstract
We present the first subquadratic algorithms for computing similarity between a pair of point sequences in R^d, for any fixed d > 1, using dynamic time warping (DTW) and edit distance, assuming that the point sequences are drawn from certain natural families of curves. In particular, our algorithms compute (1 + eps)-approximations of DTW and ED in near-linear time for point sequences drawn from k-packed or k-bounded curves, and subquadratic time for backbone sequences. Roughly speaking, a curve is k-packed if the length of its intersection with any ball of radius r is at most kr, and it is k-bounded if the sub-curve between two curve points does not go too far from the two points compared to the distance between the two points. In backbone sequences, consecutive points are spaced at approximately equal distances apart, and no two points lie very close together. Recent results suggest that a subquadratic algorithm for DTW or ED is unlikely for an arbitrary pair of point sequences even for d = 1. The commonly used dynamic programming algorithms for these distance measures reduce the problem to computing a minimum-weight path in a grid graph. Our algorithms work by constructing a small set of rectangular regions that cover the grid vertices. The weights of vertices inside each rectangle are roughly the same, and we develop efficient procedures to compute the approximate minimum-weight paths through these rectangles.
Cite as

Pankaj K. Agarwal, Kyle Fox, Jiangwei Pan, and Rex Ying. Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2016.6,
  author =	{Agarwal, Pankaj K. and Fox, Kyle and Pan, Jiangwei and Ying, Rex},
  title =	{{Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{6:1--6: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.6},
  URN =		{urn:nbn:de:0030-drops-58989},
  doi =		{10.4230/LIPIcs.SoCG.2016.6},
  annote =	{Keywords: Dynamic time warping, Edit distance, Near-linear-time algorithm, Dynamic programming, Well-separated pair decomposition}
}
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}
}
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