CanaDAM 2015
Université de la Saskatchewan, 1 - 4 juin 2015

Algorithms and complexity

BUNDIT LAEKHANUKIT, IDSIA - Istituto Dalle Molle di Studi sull'Intelligenza Artificiale
On Survivable Set Connectivity  [PDF]

In the Survivable Set Connectivity problem (SSC), given an $n$-node edge-weighted undirected graph $G$ and $h$ set pairs $(S_i,T_i)\subseteq V(G)\times V(G)$ with integer $k_i>0$, we wish to find a min-cost subgraph $H$: $\forall i$, $H$ has $k_i$ edge-disjoint $S_i,T_i$-paths. We show

- Approximating SSC to a factor of $2^{\log^{1-\epsilon}n}, \forall \epsilon > 0$, is Quasi-NP-hard.

- An algorithm that finds $H$ with $\mathrm{cost}(H) \leq \mathrm{opt} \cdot \mathrm{polylog}(nh)$ and connectivity $\geq k_i / \log n$ for all $(S_i,T_i)$. So, by relaxing connectivity, we obtain a cost-guarantee beyond the lower bound.

This is a joint work with Parinya Chalermsook and Fabrizio Grandoni.

JOSEPH MANNING, University College Cork, Ireland
Linear-Time Canonical Encoding of Plane Graphs  [PDF]

This talk introduces a canonical string representation for plane graphs, (an \emph{encoding}), and presents a simple linear-time algorithm for its construction. Applications include linear-time algorithms to reveal plane graph isomorphism, to partition a set of plane graphs into isomorphism classes, and to determine all axial and rotational symmetries of a plane graph.

GARA PRUESSE, Vancouver Island University
The Most Elegant Algorithm for the Bump-Number of a Poset  [PDF]

The bump number problem on posets is that of finding a linear extension that minimizes the number of adjacent elements that are comparable. The problem was the subject of significant research until an algorithm was found that runs in linear time (Gabow, 1982; Gabow and Tarjan 1988). No algorithm could be faster; however, the algorithms given are extremely complex. In this talk the author presents a simple, easily implemented algorithm that is “nearly linear time”. Our algorithms and proofs offer insight into the mysterious effectiveness of Lexicographic Depth-First Search as a preprocessing step for certain algorithms on cocomparability graphs.

RAIMI RUFAI, George Mason University
A Simple Convex Layers Algorithm  [PDF]

Given a set of points $P$ in the plane, we say the convex hull of $P$ is the first layer $L_1$ of $P$. So, in general a point $p$ belongs to layer $L_i$, if it lies on the convex hull of the point set $P \setminus \bigcup_{j=1}^{i-1}\{L_j\}$. The \textit{convex layers problem} is to compute these layers.

Previous optimal algorithms for this problem have been complex. This paper presents a simple $\mathcal{O}\left(n \log n\right)$-time and linear space algorithm for this problem. Our algorithm first computes four quarter convex layers using a plane-sweep paradigm and then merges these layers in linear time.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Saskatchewan