Skip to main content

Research Repository

Advanced Search

All Outputs (2833)

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.

Self-Organising Maps for Implicit Surface Reconstruction (2008)
Presentation / Conference Contribution
Yoon, M., Ivrissimtzis, I., & Lee, S. (2008). Self-Organising Maps for Implicit Surface Reconstruction. In I. S. Lim, & W. Tang (Eds.),

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.

Caterpillar duality for constraint satisfaction problems (2008)
Presentation / Conference Contribution
Carvalho, C., Dalmau, V., & Krokhin, A. (2008). Caterpillar duality for constraint satisfaction problems. In Twenty-third Annual IEEE Symposium on Logic in Computer Science, 24-27 June 2008, Pittsburgh, PA ; proceedings (307 -316). https://doi.org/10.1109/lics.2008.19

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

Complexity of Decoding Gabidulin Codes (2008)
Presentation / Conference Contribution
Gadouleau, M., & Yan, Z. (2008). Complexity of Decoding Gabidulin Codes. In Proc. IEEE CISS (1081-1085)

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.

MacWilliams Identity for Codes with the Rank Metric (2008)
Journal Article
Gadouleau, M., & Yan, Z. (2008). MacWilliams Identity for Codes with the Rank Metric. EURASIP Journal on Wireless Communications and Networking, 2008, Article 754021. https://doi.org/10.1155/2008/754021

The MacWilliams identity, which relates the weight distribution of a code to the weight distribution of its dual code, is useful in determining the weight distribution of codes. In this paper, we derive the MacWilliams identity for linear codes with... Read More about MacWilliams Identity for Codes with the Rank Metric.