Outputs (127)

Balls into non-uniform bins (2014)
Journal Article
Berenbrink, P., Brinkmann, A., Friedetzky, T., & Nagel, L. (2014). Balls into non-uniform bins. Journal of Parallel and Distributed Computing, 74(2), 2065-2076. https://doi.org/10.1016/j.jpdc.2013.10.008

Balls-into-bins games for uniform bins are widely used to model randomised load balancing strategies. Recently, balls-into-bins games have been analysed under the assumption that the selection probabilities for bins are not uniformly distributed. The... Read More about Balls into non-uniform bins.

A reconfigurable, regular-topology cluster/datacenter network using commodity optical switches (2014)
Journal Article
Lugones, D., Katrinis, K., Theodoropoulos, G., & Collier, M. (2014). A reconfigurable, regular-topology cluster/datacenter network using commodity optical switches. Future Generation Computer Systems, 30, https://doi.org/10.1016/j.future.2013.04.016

Hardware-aware block size tailoring on adaptive spacetree grids for shallow water waves (2014)
Presentation / Conference Contribution
Weinzierl, T., Wittmann, R., Unterweger, K., Bader, M., Breuer, A., & Rettenberger, S. (2014, January). Hardware-aware block size tailoring on adaptive spacetree grids for shallow water waves. Presented at HiStencils 2014 - 1st International Workshop on High-Performance Stencil Computations, Vienna, Austria

Spacetrees are a popular formalism to describe dynamically adaptive Cartesian grids. Though they directly yield an adaptive spatial discretisation, i.e. a mesh, it is often more efficient to augment them by regular Cartesian blocks embedded into the... Read More about Hardware-aware block size tailoring on adaptive spacetree grids for shallow water waves.

Colias: An Autonomous Micro Robot for Swarm Robotic Applications (2014)
Journal Article
Arvin, F., Murray, J., Zhang, C., & Yue, S. (2014). Colias: An Autonomous Micro Robot for Swarm Robotic Applications. International Journal of Advanced Robotic Systems, 11(7), https://doi.org/10.5772/58730

Robotic swarms that take inspiration from nature are becoming a fascinating topic for multi-robot researchers. The aim is to control a large number of simple robots in order to solve common complex tasks. Due to the hardware complexities and cost of... Read More about Colias: An Autonomous Micro Robot for Swarm Robotic Applications.

Parameterized Domination in Circle Graphs (2014)
Journal Article
Bousquet, N., Gonçalves, D., Mertzios, G., Paul, C., Sau, I., & Thomassé, S. (2014). Parameterized Domination in Circle Graphs. Theory of Computing Systems, 54(1), 45-72. https://doi.org/10.1007/s00224-013-9478-8

A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Appl. Math., 42(1):51–63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of ou... Read More about Parameterized Domination in Circle Graphs.

Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs (2014)
Journal Article
Bonamy, M., Johnson, M., Lignos, I., Patel, V., & Paulusma, D. (2014). Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. Journal of Combinatorial Optimization, 27(1), 132-143. https://doi.org/10.1007/s10878-012-9490-y

A k-colouring of a graph G=(V,E) is a mapping c:V→{1,2,…,k} such that c(u)≠c(v) whenever uv is an edge. The reconfiguration graph of the k-colourings of G contains as its vertex set the k-colourings of G, and two colourings are joined by an edge if t... Read More about Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs.

Lift-contractions (2014)
Journal Article
Golovach, P., Paulusma, D., Kaminski, M., & Thilikos, D. (2014). Lift-contractions. European Journal of Combinatorics, 35, 286-296. https://doi.org/10.1016/j.ejc.2013.06.026

We introduce and study a partial order on graphs—lift-contractions. A graph H is a lift-contraction of a graph G if H can be obtained from G by a sequence of edge lifts and edge contractions. We give sufficient conditions for a connected graph to con... Read More about Lift-contractions.

Knocking Out P_k-free Graphs (2014)
Presentation / Conference Contribution
Johnson, M., Paulusma, D., & Stewart, A. (2014, December). Knocking Out P_k-free Graphs. Presented at 39th International Symposium, MFCS 2014, Budapest, Hungary

A parallel knock-out scheme for a graph proceeds in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is KO-reducible if there exists such a scheme that eliminates every vertex in the graph. The Paralle... Read More about Knocking Out P_k-free Graphs.

Finding Shortest Paths Between Graph Colourings (2014)
Presentation / Conference Contribution
Johnson, M., Kratsch, D., Kratsch, S., Patel, V., & Paulusma, D. (2014, December). Finding Shortest Paths Between Graph Colourings. Presented at 9th International Symposium, IPEC 2014, Wroclaw, Poland

A Reconfigurations Analogue of Brooks’ Theorem (2014)
Presentation / Conference Contribution
Feghali, C., Johnson, M., & Paulusma, D. (2014, December). A Reconfigurations Analogue of Brooks’ Theorem. Presented at 39th International Symposium, MFCS 2014, Budapest, Hungary

Let G be a simple undirected graph on n vertices with maximum degree Δ. Brooks’ Theorem states that G has a Δ-colouring unless G is a complete graph, or a cycle with an odd number of vertices. To recolour G is to obtain a new proper colouring by chan... Read More about A Reconfigurations Analogue of Brooks’ Theorem.