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.
44916266
Inversion of Cycle Index Sum Relations for 2- and 3-Connected Graphs
Abstract Algebraic inversion of cycle index sum relations is employed to derive new algorithms for counting unlabeled 2-connected graphs, homeomorphically irreducible 2-connected graphs, and 3-connected graphs. The new algorithms are significantly more efficient than earlier ones, both asymptotically and for modest values of the order. Tables of computed results are included.
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.
15896133
Worst-Case Analysis of Read's Chromatic Polynomial Algorithm
The worst-case time-complexity of Read's edge-addition/contraction algorithm for computing the chromatic polynomial of an n-vertex graph is shown to be O(n2B(n)), where B(n) is the nth Bell number, which grows faster than cn for any c but slower than n!. The factor n2 can be reduced to n, and the space-complexity from O(n3) to O(n2), by storing in arrays the information needed to reverse each transformation made on the graph. A graph G is assumed to be finite (with n vertices), unoriented and without loops or parallel edges. A t-colouring of G is a mapping from the vertex-set of G into the set {1,...,t} of colours so that no two adjacent vertices have the same colour. The chromatic polynomial P(G,t) of G is a function of t whose value for a given t is the number of t-colourings of G. Once the polynomial P(G,t) has been calculated, one can decide in polynomial time if G has a t-colouring for a given t by substituting t into the polynomial: G has a t-colouring if and only if P(G,t)>0. Since the problem of deciding whether G has a t-colouring is NP-hard [1, p. 392], it is unlikely that a polynomial-time algorithm will be found for computing the chromatic polynomial of a graph. The most commonly-used algorithm is the one proposed by Read [3]. It has been referenced and improved upon in several places in the literature (see, for example [5]) but its worst-case timeand spacecomplexity have never been published. We show here that the spacecomplexity is O(n3) and the time-complexity is O(n2B(n)), where B(n), the nth Bell number, grows faster than cn for any c but slower than n!, and we modify the algorithm so that it runs in O(nB(n)) time and uses O(n2) space. The following facts are shown in [3] and in other places: 1. P(G,t) is a polynomial of degree n in t. 2. If G is a tree then P(G,t)=t(t-1)n-1. 3. If G is not connected then the chromatic polynomial of G is the product of the chromatic polynomials of its connected components. 4. If G is a complete graph then P(G,t) = t(t-1)(t-2)...(t-n+1). (1) 5. If G is not a complete graph, let x and y be any two non-adjacent vertices. Let G+{x,y} be the graph obtained from G by adding the edge {x,y} to G. Let G(x=y) be the graph obtained from G by identifying the vertices x and y, where a vertex v is adjacent to the common vertex xy in G(x=y) if and only if v is adjacent to at least one of x and y in G. Then P(G,t) = P(G+{x,y},t) + P(G(x=y),t). (2) The algorithm in [3] for calculating P(G,t) is a recursive one based on (1) and (2). We give a non-recursive version (see Figure 1) for the purpose of analysing its spaceand time-complexity. Procedure PolyChrome(G: n-vertex graph; C: ARRAY[1..n] OF INTEGER); FOR i:=1 TO n DO C[i]:=0 END FOR; m:=n; H:=G; (* H is the current graph, which has m vertices *) Stack:=EMPTY; LOOP IF H has two non-adjacent vertices x and y THEN PUSH H+{x,y} onto Stack; H:=H(x=y); m:=m-1; ELSE C[m]:=C[m]+1; IF m<n THEN POP from Stack into H; m:=m+1; ELSE EXIT END IF END IF END LOOP END PolyChrome. Figure 1 A non-recursive version of Read's chromatic polynomial algorithm. We find P(G,t) from formula (3) below: P(G,t) = C[1]t + C[2]t(t-1) + ... + C[n]t(t-1)...(t-n+1). (3) We analyse the spaceand time-complexity of this algorithm under the assumption that the graph is represented by an adjacency matrix. The space-complexity is easy to analyse: at any time the stack will contain one graph with i vertices for each i from n down to m for a maximum of n graphs, each occupying O(n2) space, for a total of O(n3). To analyse the time-complexity we note that everything done to a graph H creating it, searching it for non-adjacent vertices, pushing it onto the stack and popping it off again takes O(n2) elementary operations, so that the total number of operations performed is O(n2) multiplied by the number of graphs the algorithm has to treat. The branching tree for this algorithm is a binary tree whose nodes are the graphs H the algorithm has to treat, with G as its root and the complete graphs as its leaves, and each internal node H for which the nonadjacent vertices x and y have been found has H+{x,y} and H(x=y) as its children. Each time the algorithm treats a complete graph it increases C[m] by 1 for some m, 1≤m≤n, so that the number of complete graphs it treats is C[1] + C[2] + ... + C[n], (4) and since the total number of nodes of a binary tree is twice the number of its leaves minus 1, the total time complexity of the algorithm is O(n2 multiplied by the sum in (4)). The worst case of this algorithm clearly occurs when G has no edges. In this case P(G,t)=tn. Substituting this value of P(G,t) into (3) we find that for each value of k, C[k]=S(n,k), a Stirling number of the second kind [4, p. 33]. Substituting these values into (4) we obtain the Bell number B(n). The worstcase time-complexity of this algorithm is thus O(n2B(n)). There is an asymptotic estimate for B(n) in [2]: B(n) ~ (R+1)-1/2exp[n(R+R-1-1)-1], (5)
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.
28528633
Total Vertex Enumeration in Rooted Planar Maps
7417163
Easy Problems are Sometimes Hard
We present a detailed experimental investigation of the easy-hard-easy phase transition for randomly generated instances of satisfiability problems. Problems in the hard part of the phase transition have been extensively used for benchmarking satisfiability algorithms. This study demonstrates that problem classes and regions of the phase transition previously thought to be easy can sometimes be orders of magnitude more difficult than the worst problems in problem classes and regions of the phase transition considered hard. These difficult problems are either hard unsatisfiable problems or are satisfiable problems which give a hard unsatisfiable subproblem following a wrong split. Whilst these hard unsatisfiable problems may have short proofs, these appear to be difficult to find, and other proofs are long and hard.
1960492
Challenges in securing voice over IP
Although VoIP offers lower cost and greater flexibility, it can also introduce significant risks and vulnerabilities. This article explains the challenges of VoIP security and outlines steps for helping to secure an organization's VoIP network.
2991975
Improved Algorithm for Finding (a, b)-Super Solutions
Super solutions are a mechanism to provide robustness to constraint programs. We introduce a new algorithm that exploits the similarity between a super solution and its repairs in order to do inference during search. It improves on previous methods since it is more space efficient and also faster in practice.
6579174
The Scaling of Search Cost
We show that a rescaled constrainedness parameter provides the basis for accurate numerical models of search cost for both backtracking and local search algorithms. In the past, the scaling of performance has been restricted to critically constrained problems at the phase transition. Here, we show how to extend models of search cost to the full width of the phase transition. This enables the direct comparison of algorithms on both under-constrained and over-constrained problems. We illustrate the generality of the approach using three different problem domains (satisfiability, constraint satisfaction and travelling salesperson problems) with both backtracking algorithms like the Davis-Putnam procedure and local search algorithms like GSAT. As well as modelling data from experiments, we give accurate predictions for results beyond the range of the experiments.
3264013
Symmetry Breaking Using Value Precedence
We present a comprehensive study of the use of value precedence constraints to break value symmetry. We first give a simple encoding of value precedence into ternary constraints that is both efficient and effective at breaking symmetry. We then extend value precedence to deal with a number of generalizations like wreath value and partial interchangeability. We also show that value precedence is closely related to lexicographical ordering. Finally, we consider the interaction between value precedence and symmetry breaking constraints for variable symmetries.