We investigate the phase transition in vertex coloring on random graphs, using the extremal optimization heuristic. Three-coloring is among the hardest combinatorial optimization problems and is equivalent to a 3-stat...
详细信息
We investigate the phase transition in vertex coloring on random graphs, using the extremal optimization heuristic. Three-coloring is among the hardest combinatorial optimization problems and is equivalent to a 3-state anti-ferromagnetic Potts model. Like many other such optimization problems, it has been shown to exhibit a phase transition in its ground state behavior under variation of a system parameter: the graph’s mean vertex degree. This phase transition is often associated with the instances of highest complexity. We use extremal optimization to measure the ground state cost and the “backbone,” an order parameter related to ground state overlap, averaged over a large number of instances near the transition for random graphs of size n up to 512. For these graphs, benchmarks show that extremal optimization reaches ground states and explores a sufficient number of them to give the correct backbone value after about O(n3.5) update steps. Finite size scaling yields a critical mean degree value αc=4.703(28). Furthermore, the exploration of the degenerate ground states indicates that the backbone order parameter, measuring the constrainedness of the problem, exhibits a first-order phase transition.
In this paper the problem of constructing algorithms for comparing knots and links is discussed. A survey of existing approaches and basic results in this area is given. In particular, diverse combinatorial methods fo...
详细信息
In this paper the problem of constructing algorithms for comparing knots and links is discussed. A survey of existing approaches and basic results in this area is given. In particular, diverse combinatorial methods for representing links are discussed, the Haken algorithm for recognizing a trivial knot (the unknot) and a scheme for constructing a general algorithm (using Haken's ideas) for comparing links are presented, an approach based on representing links by closed braids is described, the known algorithms for solving the word problem and the conjugacy problem for braid groups are described, and the complexity of the algorithms under consideration is discussed. A new method of combinatorial description of knots is given together with a new algorithm (based on this description) for recognizing the unknot by using a procedure for monotone simplification. In the conclusion of the paper several problems are formulated whose solution could help to advance towards the 'algorithmization' of knot theory.
Let [a,b] be a line segment with end points a, b and ν a point at which a viewer is located, all in R 3. The aperture angle of [a,b] from point ν, denoted by θ(ν), is the interior angle at ν of the triangle Δ(a...
详细信息
We propose fully dynamic algorithms for maintaining the distances and the shortest paths from a single source in either a directed or an undirected graph with positive real edge weights, handling insertions, deletions...
详细信息
We propose fully dynamic algorithms for maintaining the distances and the shortest paths from a single source in either a directed or an undirected graph with positive real edge weights, handling insertions, deletions, and weight updates of edges. The algorithms require linear space and optimal query time. The cost of the update operations depends on the class of the considered graph and on the number of the output updates, i.e., on the number of vertices that, due to an edge modification, either change the distance from the source or change the parent in the shortest paths tree. We first show that, if we deal only with updates on the weights of edges, then the update procedures require O(log n) worst case time per output update for several classes of graphs, as in the case of graphs with bounded genus, bounded arboricity, bounded degree, bounded treewidth, and bounded pagenumber. For general graphs with n vertices and m edges the algorithms require O(root m log n) worst case time per output update. We also show that, if insertions and deletions of edges are allowed, then similar amortized bounds hold. (C) 2000 Academic Press.
We propose a model of database programming with reflection (dynamic generation of queries within the host programming language), called the reflective relational machine, and characterize the power of this machine in ...
详细信息
We propose a model of database programming with reflection (dynamic generation of queries within the host programming language), called the reflective relational machine, and characterize the power of this machine in terms of known complexity classes. In particular, the polynomial-time restriction of the reflective relational machine is shown to express PSPACE, and to correspond precisely to uniform circuits of polynomial depth and exponential size. This provides an alternative, logic-based formulation of the uniform circuit model, which may be more convenient for problems naturally formulated in logic terms, and establishes that reflection allows for more "intense" parallelism, which is not attainable otherwise (unless P = PSPACE). We also explore the power of the reflective relational machine subject to restrictions on the number of variables used, emphasizing the case of sublinear bounds. (C) 1998 Academic Press.
A basic feature of Terminological Knowledge Representation Systems is to represent knowledge by means of taxonomies, here called terminologies, and to provide a specialized reasoning engine to do inferences on these s...
详细信息
A basic feature of Terminological Knowledge Representation Systems is to represent knowledge by means of taxonomies, here called terminologies, and to provide a specialized reasoning engine to do inferences on these structures, The taxonomy is built through a representation language called a concept language (or description logic), which is given a well-defined set-theoretic semantics. The efficiency of reasoning has often been advocated as a primary motivation for the use of such systems. The main contributions of the paper are: (1) a complexity analysis of concept satisfiability and subsumption for a wide class of concept languages;(2) algorithms for these inferences that comply with the worst-case complexity of the reasoning task they perform. (C) 1997 Academic Press.
暂无评论