Outputs (71)

A multi-level hypergraph partitioning algorithm using rough set clustering (2015)
Book Chapter
Lotfifar, F., & Johnson, M. (2015). A multi-level hypergraph partitioning algorithm using rough set clustering. In J. Träff, S. Hunold, & F. Versaci (Eds.), Euro-Par 2015 : parallel processing : 21st International Conference on Parallel and Distributed Computing, Vienna, Austria, August 24-28, 2015, Proceedings (159-170). Springer Verlag. https://doi.org/10.1007/978-3-662-48096-0_13

The hypergraph partitioning problem has many applications in scientific computing and provides a more accurate inter-processor communication model for distributed systems than the equivalent graph problem. In this paper, we propose a sequential multi... Read More about A multi-level hypergraph partitioning algorithm using rough set clustering.

Finding Shortest Paths Between Graph Colourings (2015)
Journal Article
Johnson, M., Kratsch, D., Kratsch, S., Patel, V., & Paulusma, D. (2016). Finding Shortest Paths Between Graph Colourings. Algorithmica, 75(2), 295-321. https://doi.org/10.1007/s00453-015-0009-7

The k-colouring reconguration problem asks whether, for a given graph G, two proper k-colourings and of G, and a positive integer `, there exists a sequence of at most ` + 1 proper k-colourings of G which starts with and ends with and where successiv... Read More about Finding Shortest Paths Between Graph Colourings.

Algorithms for diversity and clustering in social networks through dot product graphs (2015)
Journal Article
Johnson, M., Paulusma, D., & van Leeuwen, E. (2015). Algorithms for diversity and clustering in social networks through dot product graphs. Social Networks, 41, 48-55. https://doi.org/10.1016/j.socnet.2015.01.001

In this paper, we investigate a graph-theoretical model of social networks. The dot product model assumes that two individuals are connected in the social network if their attributes or opinions are similar. In the model, a d -dimensional vector View... Read More about Algorithms for diversity and clustering in social networks through dot product graphs.

Smart grid-aware scheduling in data centres (2015)
Presentation / Conference Contribution
Mäsker, M., Nagel, L., Brinkmann, A., Lotfifar, F., & Johnson, M. (2015, December). Smart grid-aware scheduling in data centres. Presented at 2015 Sustainable Internet and ICT for Sustainability (SustainIT), Madrid, Spain

In several countries the expansion and establishment of renewable energies result in widely scattered and often weather-dependent energy production, decoupled from energy demand. Large, fossil-fuelled power plants are gradually replaced by many small... Read More about Smart grid-aware scheduling in data centres.

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.

Finding paths between 3-colorings (2011)
Journal Article
Cereceda, L., van den Heuvel, J., & Johnson, M. (2011). Finding paths between 3-colorings. Journal of Graph Theory, 67(1), 69-82. https://doi.org/10.1002/jgt.20514

Given a 3-colorable graph G together with two proper vertex 3-colorings α and β of G, consider the following question: is it possible to transform α into β by recoloring vertices of G one at a time, making sure that all intermediate colorings are pro... Read More about Finding paths between 3-colorings.

Obtaining online ecological colourings by generalizing first-fit (2010)
Presentation / Conference Contribution
Johnson, M., Patel, V., Paulusma, D., & Trunck, T. (2010, December). Obtaining online ecological colourings by generalizing first-fit. Presented at 5th International Computer Science Symposium in Russia (CSR 2010), Kazan, Russia

A colouring of a graph is ecological if every pair of vertices that have the same set of colours in their neighbourhood are coloured alike. We consider the following problem: if a graph G and an ecological colouring c of G are given, can further vert... Read More about Obtaining online ecological colourings by generalizing first-fit.

Mixing 3-colourings in bipartite graphs (2009)
Journal Article
Cereceda, L., van den Heuvel, J., & Johnson, M. (2009). Mixing 3-colourings in bipartite graphs. European Journal of Combinatorics, 30(7), 1593-1606. https://doi.org/10.1016/j.ejc.2009.03.011

For a 3-colourable graph G, the 3-colour graph of G, denoted C_3(G), is the graph with node set the proper vertex 3-colourings of G, and two nodes adjacent whenever the corresponding colourings differ on precisely one vertex of G. We consider the fol... Read More about Mixing 3-colourings in bipartite graphs.

Upper bounds and algorithms for parallel knock-out numbers (2009)
Journal Article
Broersma, H., Johnson, M., & Paulusma, D. (2009). Upper bounds and algorithms for parallel knock-out numbers. Theoretical Computer Science, 410(14), 1319-1327. https://doi.org/10.1016/j.tcs.2008.03.024

We study parallel knock-out schemes for graphs. These schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the... Read More about Upper bounds and algorithms for parallel knock-out numbers.

Connectedness of the graph of vertex-colourings (2008)
Journal Article
Cereceda, L., van den Heuvel, J., & Johnson, M. (2008). Connectedness of the graph of vertex-colourings. Discrete Mathematics, 308(5-6), 913-919. https://doi.org/10.1016/j.disc.2007.07.028

For a positive integer k and a graph G, the k-colour graph of G , Ck(G), is the graph that has the proper k-vertex-colourings of G as its vertex set, and two k -colourings are joined by an edge in Ck(G) if they differ in colour on just one vertex of... Read More about Connectedness of the graph of vertex-colourings.