Skip to main content

Research Repository

Advanced Search

Outputs (75)

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.

Caterpillar duality for constraint satisfaction problems (2008)
Presentation / Conference Contribution
Carvalho, C., Dalmau, V., & Krokhin, A. (2008, June). Caterpillar duality for constraint satisfaction problems. Presented at 23rd Annual IEEE Symposium on Logic in Computer Science (LICS) 2008, Pittsburgh, Pennsylvania

The study of constraint satisfaction problems definable in various fragments of Datalog has recently gained considerable importance. We consider constraint satisfaction problems that are definable in the smallest natural recursive fragment of Datalog... Read More about Caterpillar duality for constraint satisfaction problems.

Self-Organising Maps for Implicit Surface Reconstruction (2008)
Presentation / Conference Contribution
Yoon, M., Ivrissimtzis, I., & Lee, S. (2008, June). Self-Organising Maps for Implicit Surface Reconstruction. Presented at 6th Theory and Practice of Computer Graphics, Manchester, UK

This paper proposes an implicit surface reconstruction algorithm based on Self-Organising Maps (SOMs). The SOM has the connectivity of a regular 3D grid, each node storing its signed distance from the surface. At each iteration of the basic algorithm... Read More about Self-Organising Maps for Implicit Surface Reconstruction.

A new characterization of P6-free graphs (2008)
Presentation / Conference Contribution
Hof, P. V., & Paulusma, D. (2008, December). A new characterization of P6-free graphs. Presented at 14th Annual International Computing and Combinatorics Conference, Dalian, China

We study P 6-free graphs, i.e., graphs that do not contain an induced path on six vertices. Our main result is a new characterization of this graph class: a graph G is P 6-free if and only if each connected induced subgraph of G on more than one vert... Read More about A new characterization of P6-free graphs.

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.