7 citations · 14 across the 12 of their papers we have counts for
6 papers · 1 filter
Graph Inference with Effective Resistance Queries
Huck Bennett, Mitchell Black, Amir Nayyeri +1
The goal of graph inference is to design algorithms for learning properties of a hidden graph using queries to an oracle that returns information about the graph. Graph reconstruct…
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 Cuts in Surface Graphs
Erin W. Chambers, Jeff Erickson, Kyle Fox +1
We describe algorithms to efficiently compute minimum -cuts and global minimum cuts of undirected surface-embedded graphs. Given an edge-weighted undirected graph with $…
Minimum cycle and homology bases of surface embedded graphs
Glencora Borradaile, Erin Wolf Chambers, Kyle Fox +1
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…
Towards single face shortest vertex-disjoint paths in undirected planar graphs
Glencora Borradaile, Amir Nayyeri, Farzad Zafarani
Given pairs of terminals in a graph , the min-sum vertex-disjoint paths problem is to find a collection $\{Q_{1}, Q_{2}, \ld…