14691140
Counting unlabelled three-connected and homeomorphically irreducible two-connected graphs
A graph will be assumed to be finite and unoriented, with no loops or multiple edges; if multiple edges are to be allowed, the term multigraph will be used. A graph or multigraph. will be called k-connected if at least k vertices and their incident edges must be removed to disconnect it (a complete graph is considered to be k-connected for any k). A block (respectively, multiblock) is a 2-connected graph (respectively, multigraph) with at least 2 vertices, and a brick is a 3-connected graph with at least 4 vertices. A Iabelling of a graph or multigraph with n vertices is a l-l correspondence from the set { 1, 2,..., n} onto the set of its vertices. Let A(x, y) be the mixed exponential generating function C,,, An,,,,x”.vmln!, where A,,, is the number of labelled graphs with n vertices and m edges, and let C(x, y) and B(x, y) be analogous generating functions which count labelled connected graphs and labelled blocks, respectively. The following formulae, due to Riddell [lo], appear in one-variable form in [6, pp. 3-111:
28528633
Total Vertex Enumeration in Rooted Planar Maps
8458935
Efficient enumeration of sensed planar maps
We use Liskovets' quotient maps and Robinson's cycle index sums to count 1-, 2- and 3-connected planar maps by number of vertices and edges up to sense-preserving homeomorphism of the embedding sphere. Although Wormald has already counted these maps up to all homeomorphism, sense-reversing as well as sense-preserving, our methods are computationally more efficient for counting these maps up to orientation-preserving homeomorphism and yield closed-form enumeration formulas in the case of 1- and 2-connected maps. Our formula for 1-connected planar maps uses the number of rooted planar maps with i+1 vertices and j+1 faces; we evaluate these numbers using a method that is more efficient than substituting into Tutte's parametric equations, and we also count rooted toroidal maps by number of vertices and faces more efficiently than by substituting into Arques' explicit formula.
18489826
Counting unrooted loopless planar maps
We present a formula for the number of n-edge unrooted loopless planar maps considered up to orientation-preserving isomorphism. The only sum contained in this formula is over the divisors of n.
15854568
Enumeration of eulerian and unicursal planar maps
Sum-free enumerative formulae are derived for several classes of rooted planar maps with no vertices of odd valency (eulerian maps) and with two vertices of odd valency (unicursal maps). As corollaries we obtain simple formulae for the numbers of unrooted eulerian and unicursal planar maps. Also, we obtain a sum-free formula for the number of rooted bi-eulerian (eulerian and bipartite) maps and some related results.
16903920
A Calculus for Rippling
We present a calculus for rippling, a special type of rewriting using annotations. These annotations guide the derivation towards a particular goal. Although it has been suggested that rippling can be implemented directly via first-order term rewriting, we demonstrate that this is not possible. We show how a simple change to subterm replacement and matching gives a calculus for implementing rippling. This calculus also allows us to combine rippling with conventional term rewriting. Such a combination offers the flexibility and uniformity of conventional rewriting with the highly goal-directed nature of rippling. The calculus we present here is implemented and has been integrated into the Edinburgh CLAM proof-planning system.
507124
Constraint-Based Preferential Optimization
We first show that the optimal and undominated outcomes of an unconstrained (and possibly cyclic) CP-net are the solutions of a set of hard constraints. We then propose a new algorithm for finding the optimal outcomes of a constrained CP-net which makes use of hard constraint solving. Unlike previous algorithms, this new algorithm works even with cyclic CP-nets. In addition. the algorithm is not tied to CP-nets, but can work with any preference formalism which produces a preorder over the outcomes. We also propose an approximation method which weakens the preference ordering induced by the CP-net, returning a larger set of outcomes, but provides a significant computational advantage. Finally, we describe a weighted constraint approach that allows to find good solutions even when optimals do not exist.
7228681
Tetravex is NP-complete
TETRAVEX is a widely played one person computer game in which you are given n2 unit tiles, each edge of which is labelled with a number. The objective is to place each tile within a n by n square such that all neighbouring edges are labelled with an identical number. Unfortunately, playing TETRAVEX is computationally hard. More precisely, we prove that deciding if there is a tiling of the TETRAVEX board given n2 unit tiles is NP-complete. Deciding where to place the tiles is therefore NP-hard. This may help to explain why TETRAVEX is a good puzzle. This result compliments a number of similar results for one person games involving tiling. For example, NP-completeness results have been show for: the offline version of Tetris [1], KPlumber (which involves rotating tiles containing drawings of pipes to make a connected network) [2], and shortest sliding puzzle problems [3]. It raises a number of open questions. For example, is the infinite version Turing-complete? How do we generate TETRAVEX problems which are truly puzzling as random NP-complete problems are often surprising easy to solve? Can we observe phase transition behaviour? What about the complexity of the problem when it is guaranteed to have an unique solution? How do we generate puzzles with unique solutions?
3250202
The Range Constraint: Algorithms and Implementation
We recently proposed a simple declarative language for specifying a wide range of counting and occurrence constraints. The language uses just two global primitives: the Range constraint, which computes the range of values used by a set of variables, and the Roots constraint, which computes the variables mapping onto particular values. In order for this specification language to be executable, propagation algorithms for the Range and Roots constraints should be developed. In this paper, we focus on the study of the Range constraint. We propose an efficient algorithm for propagating the Range constraint. We also show that decomposing global counting and occurrence constraints using Range is effective and efficient in practice.
7309498
mCP Nets: Representing and Reasoning with Preferences of Multiple Agents
We introduce mCP nets, an extension of the CP net formalism to model and handle the qualitative and conditional preferences of multiple agents. We give a number of different semantics for reasoning with mCP nets. The semantics are all based on the idea of individual agents voting. We describe how to test optimality and preference ordering within a mCP net, and we give complexity results for such tasks. We also discuss whether the voting schemes fairly combine together the preference s of the individual agents.