Ganian, Robert Ordyniak, Sebastian
Published in
Algorithmica

This paper revisits the classical edge-disjoint paths (EDP) problem, where one is given an undirected graph G and a set of terminal pairs P and asks whether G contains a set of pairwise edge-disjoint paths connecting every terminal pair in P . Our aim is to identify structural properties (parameters) of graphs which allow the efficient solution of ...

Aichholzer, Oswin Cardinal, Jean Huynh, Tony Knauer, Kolja Mütze, Torsten Steiner, Raphael Vogtenhuber, Birgit
Published in
Algorithmica

Flip graphs are a ubiquitous class of graphs, which encode relations on a set of combinatorial objects by elementary, local changes. Skeletons of associahedra, for instance, are the graphs induced by quadrilateral flips in triangulations of a convex polygon. For some definition of a flip graph, a natural computational problem to consider is the fli...

Czyzowicz, Jurek Dereniowski, Dariusz Pelc, Andrzej
Published in
Algorithmica

A robot modeled as a deterministic finite automaton has to build a structure from material available to it. The robot navigates in the infinite oriented grid \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\od...

Karppa, Matti Kaski, Petteri Kohonen, Jukka Ó Catháin, Padraig
Published in
Algorithmica

We derandomize Valiant’s (J ACM 62, Article 13, 2015) subquadratic-time algorithm for finding outlier correlations in binary data. This demonstrates that it is possible to perform a deterministic subquadratic-time similarity join of high dimensionality. Our derandomized algorithm gives deterministic subquadratic scaling essentially for the same par...

Chrobak, Marek Kenyon, Claire Noga, John Young, Neal E.
Published in
Algorithmica

In the k-median problem we are given sets of facilities and customers, and distances between them. For a given set F of facilities, the cost of serving a customer u is the minimum distance between u and a facility in F. The goal is to find a set F of k facilities that minimizes the sum, over all customers, of their service costs. Following the work...

Mnich, Matthias Schlotter, Ildikó
Published in
Algorithmica

Stable matching problems with lower quotas are fundamental in academic hiring and ensuring operability of rural hospitals. Only few tractable (polynomial-time solvable) cases of stable matching with lower quotas have been identified; most such problems are \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts}...

Roth, Marc Schmitt, Johannes
Published in
Algorithmica

We investigate the problem \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\#{{\mathsf {IndSub}}}(\varPhi )$$\end{document} # IndSub ( Φ ) of counting all induced subgr...

Boissonnat, Jean-Daniel Maria, Clément
Published in
Algorithmica

This paper introduces a new data structure, called simplex tree, to represent abstract simplicial complexes of any dimension. All faces of the simplicial complex are explicitly stored in a trie whose nodes are in bijection with the faces of the complex. This data structure allows to efficiently implement a large range of basic operations on simplic...

Aziz, Haris Biró, Péter Gaspers, Serge de Haan, Ronald Mattei, Nicholas Rastegari, Baharak
Published in
Algorithmica

We consider the two-sided stable matching setting in which there may be uncertainty about the agents’ preferences due to limited information or communication. We consider three models of uncertainty: (1) lottery model—for each agent, there is a probability distribution over linear preferences, (2) compact indifference model—for each agent, a weak p...

Heuberger, Clemens Krenn, Daniel
Published in
Algorithmica

In this article, q -regular sequences in the sense of Allouche and Shallit are analysed asymptotically. It is shown that the summatory function of a regular sequence can asymptotically be decomposed as a finite sum of periodic fluctuations multiplied by a scaling factor. Each of these terms corresponds to an eigenvalue of the sum of matrices of a l...