Nil Mamano

Research Publications

Click on a publication for a brief summary.
All papers are freely available online (PDF icon).
Authors are in alphabetical order—per convention in CS theory—except when marked with "*".
See also my academic CV or my Google Scholar profile.

Conference Publications

Taming the Knight's Tour: Minimizing Turns and Crossings

J.J. Besa, T. Johnson, N. Mamano, M.C. Osegueda. FUN'20

In the knight's tour puzzle, a knight starts in the top-left corner of a chess board. The challenge is to visit every square, without repetition, usin...

Euclidean TSP, Motorcycle Graphs, and Other New Applications of Nearest-Neighbor Chains

* N. Mamano, A. Efrat, D. Eppstein, D. Frishberg, M.T. Goodrich, S. Kobourov, P. Matias, V. Polishchuk. ISAAC'19

This paper contains some of the results from the thesis on speeding up greedy algorithms (read the thesis' summary above). For instance, we improve th...

Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms

G. Barequet, D. Eppstein, M.T. Goodrich, N. Mamano. ICALP'18

Imagine that you have a set of facilities in the plane, such as post offices, and you are tasked with assigning a service region to each one, under tw...

Reactive Proximity Data Structures for Graphs

D. Eppstein, M.T. Goodrich, N. Mamano. LATIN'18

The problem in this paper is inspired by private-car services such as Uber or Lyft. We give a data structure that maintains a set of nodes in a graph ...

Defining Equitable Geographic Districts in Road Networks via Stable Matching

D. Eppstein, M.T. Goodrich, D. Korkmaz, N. Mamano. SIGSPATIAL'17 (short paper)

In theory, political districts should be balanced in population and should have compact shapes. Partisan gerrymandering is the manipulation of distric...

Algorithms for Stable Matching and Clustering in a Grid

D. Eppstein, M.T. Goodrich, N. Mamano. IWCIA'17

Whereas paper ICALP'18 gives algorithms for stable-matching Voronoi diagrams in the plane, this paper gives algorithms for such diagrams in a pixelate...

Models and Algorithms for Graph Watermarking

D. Eppstein, M.T. Goodrich, J. Lam, N. Mamano, M. Mitzenmacher, M. Torres. ISC'16 (best student paper award)

Watermarking is more commonly known in the context of images. There are two kinds: a visible watermark is a logo or name added on top of an image to i...

Journal Publications

Taming the Knight's Tour: Minimizing Turns and Crossings

J.J. Besa, T. Johnson, N. Mamano, M.C. Osegueda, P. Williams. TCS'22

This is a journal version of paper of the FUN'20 paper. We incorporated a contribution by a new author, Parker Williams, who improved the number of cr...

Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms

G. Barequet, D. Eppstein, M.T. Goodrich, N. Mamano. JoCG'20

This is a journal version of the ICALP'18 paper. We extended our algorithm to work for other distance metrics, such as Manhattan distance.

SANA NetGO: a combinatorial approach to using Gene Ontology (GO) terms to score network alignments

* W. Hayes, N. Mamano. Bioinformatics: Oxford Journals, 2018

Protein-protein interaction networks are graphs where the nodes represent proteins and edges denote that two proteins are physically compatible and ca...

SANA: Simulated Annealing far outperforms many other search algorithms for biological network alignment

* N. Mamano, W. Hayes. Bioinformatics: Oxford Journals, 2017

Protein-protein interaction networks are graphs where the nodes represent proteins and edges denote that two proteins can physically interact. Such gr...

PhD Dissertation

New Applications of the Nearest-neighbor Chain Algorithm

Nil Mamano

The nearest-neighbor chain algorithm was proposed in the eighties as a way to speed up certain clustering algorithms. We show that its application is ...