Skip to main content

Research Repository

Advanced Search

Outputs (40)

Retractions onto series-parallel posets (2008)
Journal Article
Dalmau, V., Krokhin, A., & Larose, B. (2008). Retractions onto series-parallel posets. Discrete Mathematics, 308(11), 2104-2114. https://doi.org/10.1016/j.disc.2006.08.010

The poset retraction problem for a poset P is whether a given poset Q containing P as a subposet admits a retraction onto P, that is, whether there is a homomorphism from Q onto P which fixes every element of P. We study this problem for finite serie... Read More about Retractions onto series-parallel posets.

Majority constraints have bounded pathwidth duality (2008)
Journal Article
Dalmau, V., & Krokhin, A. (2008). Majority constraints have bounded pathwidth duality. European Journal of Combinatorics, 29(4), 821-837. https://doi.org/10.1016/j.ejc.2007.11.020

We study certain constraint satisfaction problems which are the problems of deciding whether there exists a homomorphism from a given relational structure to a fixed structure with a majority polymorphism. We show that such a problem is equivalent to... Read More about Majority constraints have bounded pathwidth duality.

Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs (2008)
Journal Article
Bordewich, M., Karpinski, M., & Dyer, M. (2008). Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs. Random Structures and Algorithms, 32(3), 375-399. https://doi.org/10.1002/rsa.20204

We analyse the mixing time of Markov chains using path coupling with stopping times. We apply this approach to two hypergraph problems. We show that the Glauber dynamics for independent sets in a hypergraph mixes rapidly as long as the maximum degree... Read More about Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs.

Locally constrained graph homomorphisms and equitable partitions (2008)
Journal Article
Fiala, J., Paulusma, D., & Telle, J. (2008). Locally constrained graph homomorphisms and equitable partitions. European Journal of Combinatorics, 29(4), 850-880. https://doi.org/10.1016/j.ejc.2007.11.006

We explore the connection between locally constrained graph homomorphisms and degree matrices arising from an equitable partition of a graph. We provide several equivalent characterizations of degree matrices. As a consequence we can efficiently chec... Read More about Locally constrained graph homomorphisms and equitable partitions.

The computational complexity of graph contractions I: polynomially solvable and NP-complete cases (2008)
Journal Article
Levin, A., Paulusma, D., & Woeginger, G. (2008). The computational complexity of graph contractions I: polynomially solvable and NP-complete cases. Networks, 51(3), 178-189. https://doi.org/10.1002/net.20214

For a fixed pattern graph H, let H-CONTRACTIBILITY denote the problem of deciding whether a given input graph is contractible to H. This paper is part I of our study on the computational complexity of the H-CONTRACTIBILITY problem. We continue a line... Read More about The computational complexity of graph contractions I: polynomially solvable and NP-complete cases.

Emergent properties in optically bound matter (2008)
Journal Article
Taylor, J., Wong, L., Bain, C., & Love, G. (2008). Emergent properties in optically bound matter. Optics Express, 16(10), 6921-6929. https://doi.org/10.1364/oe.16.006921

Sub-micron particles have been observed to spontaneously form regular two-dimensional structures in counterpropagating evanescent laser fields. We show that collective properties of large numbers of optically-trapped particles can be qualitatively di... Read More about Emergent properties in optically bound matter.

Nature Reserve Selection Problem: A Tight Approximation Algorithm (2008)
Journal Article
Bordewich, M., & Semple, C. (2008). Nature Reserve Selection Problem: A Tight Approximation Algorithm. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 5(2), 275-280. https://doi.org/10.1109/tcbb.2007.70252

The nature reserve selection problem is a problem that arises in the context of studying biodiversity conservation. Subject to budgetary constraints, the problem is to select a set of regions to be conserved so that the phylogenetic diversity of the... Read More about Nature Reserve Selection Problem: A Tight Approximation Algorithm.

Relative length of longest paths and longest cycles in triangle-free graphs (2008)
Journal Article
Paulusma, D., & Yoshimoto, K. (2008). Relative length of longest paths and longest cycles in triangle-free graphs. Discrete Mathematics, 308(7), 1222-1229. https://doi.org/10.1016/j.disc.2007.03.070

In this paper, we study triangle-free graphs. Let G=(V,E) be an arbitrary triangle-free graph with minimum degree at least two and σ4(G)|V(G)|+2. We first show that either for any path P in G there exists a cycle C such that |VPVC|1, or G is isomorph... Read More about Relative length of longest paths and longest cycles in triangle-free graphs.

A matrix characterization of interval and proper interval graphs (2008)
Journal Article
Mertzios, G. (2008). A matrix characterization of interval and proper interval graphs. Applied Mathematics Letters, 21(4), 332-337. https://doi.org/10.1016/j.aml.2007.04.001

In this work a matrix representation that characterizes the interval and proper interval graphs is presented, which is useful for the efficient formulation and solution of optimization problems, such as the k-cluster problem. For the construction of... Read More about A matrix characterization of interval and proper interval graphs.