9 papers
Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes
Mitchell Black, Amir Nayyeri
We describe a nearly-linear time algorithm to solve the linear system parameterized by the first Betti number of the complex, where is the 1-Laplacian of a simplic…
ETH-tight algorithms for finding surfaces in simplicial complexes of bounded treewidth
Mitchell Black, Nello Blaser, Amir Nayyeri +1
Given a simplicial complex with simplices, we consider the Connected Subsurface Recognition (c-SR) problem of finding a subcomplex that is homeomorphic to a given connected sur…
On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem
Peyman Afshani, Mark de Berg, Kevin Buchin +7
We consider the following surveillance problem: Given a set of sites in a metric space and a set of robots with the same maximum speed, compute a patrol schedule of min…
Generalized max-flows and min-cuts in simplicial complexes
William Maxwell, Amir Nayyeri
We consider high dimensional variants of the maximum flow and minimum cut problems in the setting of simplicial complexes and provide both algorithmic and hardness results. By view…
Low-stretch spanning trees of graphs with bounded width
Glencora Borradaile, Erin Wolf Chambers, David Eppstein +2
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 with a linear arrange…
Minimum bounded chains and minimum homologous chains in embedded simplicial complexes
Glencora Borradaile, William Maxwell, Amir Nayyeri
We study two optimization problems on simplicial complexes with homology over , the minimum bounded chain problem: given a -dimensional complex embed…