Skip to main content

Research Repository

Advanced Search

Outputs (84)

Increasing the Minimum Degree of a Graph by Contractions (2011)
Presentation / Conference Contribution
Golovach, P., Kaminski, M., Paulusma, D., & Thilikos, D. (2011, September). Increasing the Minimum Degree of a Graph by Contractions. Presented at IPEC 2011: Parameterized and Exact Computation, Saarbrücken, Germany

Xheal: localized self-healing using expanders (2011)
Presentation / Conference Contribution
Pandurangan, G., & Trehan, A. (2011, December). Xheal: localized self-healing using expanders. Presented at Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing, New York, NY, USA

The limits of tractability in Resolution-based propositional proof systems (2011)
Journal Article
Dantchev, S., & Martin, B. (2012). The limits of tractability in Resolution-based propositional proof systems. Annals of Pure and Applied Logic, 163(3), 656-668. https://doi.org/10.1016/j.apal.2011.11.001

We study classes of propositional contradictions based on the Least Number Principle (LNP) in the refutation system of Resolution and its generalisations with bounded conjunction, Res(k). We prove that any first-order sentence with no finite models t... Read More about The limits of tractability in Resolution-based propositional proof systems.

Lift Contractions (2011)
Presentation / Conference Contribution
Golovach, P., Kamiński, M., Paulusma, D., & Thilikos, D. Lift Contractions

We introduce and study a new containment relation in graphs – lift contractions. H is a lift contraction of G if H can be obtained from G by a sequence of edge lifts and edge contractions. We show that a graph contains every n-vertex graph as a lift... Read More about Lift Contractions.

Using agents to create a university timetable addressing essential & desirable constraints and fair allocation of resources (2011)
Presentation / Conference Contribution
Wangmaeteekul, P., & Budgen, D. (2011, February). Using agents to create a university timetable addressing essential & desirable constraints and fair allocation of resources. Presented at Proceedings of the IADIS International Conference Intelligent Systems and Agents 2011, Part of the IADIS Multi Conference on Computer Science and Information Systems 2011, MCCSIS 2011, Avila, Spain

University timetabling resource allocation problems have previously been investigated using multi-agent systems. Although these studies have proposed various models, these have not addressed such issues as fairness of allocation, and of ranking const... Read More about Using agents to create a university timetable addressing essential & desirable constraints and fair allocation of resources.

On the diameter of reconfiguration graphs for vertex colourings (2011)
Presentation / Conference Contribution
Bonamy, M., Johnson, M., Lignos, I., Patel, V., & Paulusma, D. On the diameter of reconfiguration graphs for vertex colourings

The reconfiguration graph of the k-colourings of a graph G contains as its vertex set the proper vertex k-colourings of G, and two colourings are joined by an edge in the reconfiguration graph if they differ in colour on just one vertex of G. We prov... Read More about On the diameter of reconfiguration graphs for vertex colourings.

Online Regenerator Placement (2011)
Presentation / Conference Contribution
Mertzios, G., Shalom, M., Wong, P., & Zaks, S. (2011, December). Online Regenerator Placement. Presented at 15th International Conference on Principles of Distributed Systems (OPODIS), Toulouse, France

Connections between nodes in optical networks are realized by lightpaths. Due to the decay of the signal, a regenerator has to be placed on every lightpath after at most d hops, for some given positive integer d. A regenerator can serve only one ligh... Read More about Online Regenerator Placement.

Natural Models for Evolution on Networks (2011)
Presentation / Conference Contribution
Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2011, December). Natural Models for Evolution on Networks. Presented at 7th Workshop on Internet & Network Economics (WINE), Singapore

Evolutionary dynamics have been traditionally studied in the context of homogeneous populations, mainly described by the Moran process [15]. Recently, this approach has been generalized in [13] by arranging individuals on the nodes of a network (in g... Read More about Natural Models for Evolution on Networks.