| 1. |
- Angelsmark, Ola, 1972-, et al.
(författare)
-
Determining the Number of Solutions to Binary CSP Instances
- 2002
-
Ingår i: Principles and Practice of Constraint Programming, 8th International Conference CP-2002,2002. - Heidelberg : Springer Verlag. ; , s. 327-
-
Konferensbidrag (refereegranskat)abstract
- Counting the number of solutions to CSP instances has applications in several areas, ranging from statistical physics to artificial intelligence. We give an algorithm for counting the number of solutions to binary CSPs, which works by transforming the problem into a number of 2-SAT instances, where the total number of solutions to these instances is the same as those of the original problem. The algorithm consists of two main cases, depending on whether the domain size d is even, in which case the algorithm runs in O(1.3247^n*(d/2)^n) time, or odd, in which case it runs in O(1.3247^n*((d^2+d+2)/4)^(n/2)) if d=4*k+1, and O(1.3247^n*((d^2+d)/4)^(n/2)) if d=4*k+3. We also give an algorithm for counting the number of possible 3-colourings of a given graph, which runs in O(1.8171^n), an improvement over our general algorithm gained by using problem specific knowledge.
|
|
| 2. |
- Eriksson, Henrik, et al.
(författare)
-
Dense packing of patterns in a permutation
- 2007
-
Ingår i: Annals of Combinatorics. - : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 11:3-4, s. 459-470
-
Tidskriftsartikel (refereegranskat)abstract
- We study the length L-k of the shortest permutation containing all patterns of length k. We establish the bounds e(-2)k(2) < L-k <= (2/3 + o(1))k(2). We also prove that as k there are permutations of length (1/4+o(1))k(2) containing almost all patterns of length k.
|
|
| 3. |
- Gill, Jonna, et al.
(författare)
-
A regular decomposition of the edge-product space of phylogenetic trees
- 2008
-
Ingår i: Advances in Applied Mathematics. - : Elsevier BV. - 0196-8858 .- 1090-2074. ; 41:2, s. 158-176
-
Tidskriftsartikel (refereegranskat)abstract
- We investigate the topology and combinatorics of a topological space called the edge-product space that is generated by the set of edge-weighted finite labelled trees. This space arises by multiplying the weights of edges on paths in trees, and is closely connected to tree-indexed Markov processes in molecular evolutionary biology. In particular, by considering combinatorial properties of the Tuffley poset of labelled forests, we show that the edge-product space has a regular cell decomposition with face poset equal to the Tuffley poset.
|
|
| 4. |
- Gill, Jonna, et al.
(författare)
-
The k-assignment polytope
- 2009
-
Ingår i: DISCRETE OPTIMIZATION. - : Elsevier BV. - 1572-5286. ; 6:2, s. 148-161
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper we Study the structure of the k-assignment polytope, whose vertices are the m x n (0, 1)-matrices with exactly k 1:s and at most one 1 in each row and each column. This is a natural generalisation of the Birkhoff polytope and many of the known properties of the Birkhoff polytope are generalised. A representation of the faces by certain bipartite graphs is given. This tool is used to describe the properties of the polytope, especially a complete description of the cover relation in the face poset of the polytope and an exact expression for the diameter. An ear decomposition of these bipartite graphs is constructed.
|
|
| 5. |
- Gill, Jonna, 1979-
(författare)
-
The k-assignment Polytope and the Space of Evolutionary Trees
- 2004
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis consists of two papers.The first paper is a study of the structure of the k-assignment polytope, whose vertices are the m x n (0; 1)-matrices with exactly k 1:s and at most one 1 in each row and each column. This is a natural generalisation of the Birkhoff polytope and many of the known properties of the Birkhoff polytope are generalised. Two equivalent representations of the faces are given, one as (0; 1)-matrices and one as ear decompositions of bipartite graphs. These tools are used to describe properties of the polytope, especially a complete description of the cover relation in the face lattice of the polytope and an exact expression for the diameter.The second paper studies the edge-product space Є(X) for trees on X. This space is generated by the set of edge-weighted finite trees on X, and arises by multiplying the weights of edges on paths in trees. These spaces are closely connected to tree-indexed Markov processes in molecular evolutionary biology. It is known that Є(X) has a natural CW-complex structure, and a combinatorial description of the associated face poset exists which is a poset S(X) of X-forests. In this paper it is shown that the edge-product space is a regular cell complex. One important part in showing that is to conclude that all intervals [Ô, Г], Г Є S(X), have recursive coatom orderings.
|
|
| 6. |
- Håstad, Johan, et al.
(författare)
-
A smaller sleeping bag for a baby snake
- 2001
-
Ingår i: Discrete & Computational Geometry. - : Springer Science and Business Media LLC. - 0179-5376 .- 1432-0444. ; 26:1, s. 173-181
-
Tidskriftsartikel (refereegranskat)abstract
- By a sleeping bag for a baby snake in d dimensions we mean a subset of Rd which can cover, by rotation and translation, every curve of unit length. We construct sleeping bags which are smaller than any previously known in dimensions 3 and higher. In particular, we construct a three-dimensional sleeping bag of volume approximately 0.075803. For large d we construct d-dimensional sleeping bags with volume less than (cvlog d)d/d3d/2 for some constant c. To obtain the last result, we show that every curve of unit length in Rd lies between two parallel hyperplanes at distance at most C1d-3/2vlog d, for some constant c1.
|
|
| 7. |
|
|
| 8. |
- Linusson, Svante, 1969-
(författare)
-
A proof of Parisi's Conjecture
- 2003
-
Ingår i: Statistics seminar,2003.
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)
|
|
| 9. |
- Linusson, Svante, 1969-, et al.
(författare)
-
Completing a k-1 assignment
- 2004
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- We consider the distribution of the value of the optimal $k$-assignment in an $m \times n$-matrix, where the entries are independent exponential random variables with arbitrary rates. We give closed formulas for both the Laplace transform of this random variable and for its expected value under the condition that there is a zero-cost $k-1$-assignment.
|
|
| 10. |
- Linusson, Svante, 1969-, et al.
(författare)
-
Complexes of graphs with bounded matching size
- 2004
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- For positive integers $k,n$, we investigate the simplicial complex $\nmkn$ of all graphs $G$ on vertex set $[n]$ such that every matching in $G$ has size less than $k$. This complex (along with other associated cell complexes) is found to be homotopy equivalent to a wedge of spheres. The number and dimension of the spheres in the wedge are determined, and (partially conjectural) links to other combinatorially defined complexes are described. In addition we study for positive integers $r,s$ and $k$ the simplicial complex $\bnmkrs$ of all bipartite graphs $G$ on bipartition $[r] \cup [\bar{s}]$ such that there is no matching of size $k$ in $G$, and obtain results similar to those obtained for $\nmkn$.
|
|
