Search results for "Graph theory"

A graph theoretic approach to automata minimality

2012

AbstractThe paper presents a graph-theoretic approach to test the minimality of a deterministic automaton. In particular, we focus on problems concerning the dependence of the minimality of an automaton on the choice of the set F of final states or on the cardinality of the set F. We introduce different minimality conditions of an automaton and show that such conditions can be characterized in graph-theoretic terms.

Frequency Assignment and Multicoloring Powers of Square and Triangular Meshes

2005

The static frequency assignment problem on cellular networks can be abstracted as a multicoloring problem on a weighted graph, where each vertex of the graph is a base station in the network, and the weight associated with each vertex represents the number of calls to be served at the vertex. The edges of the graph model interference constraints for frequencies assigned to neighboring stations. In this paper, we first propose an algorithm to multicolor any weighted planar graph with at most $\frac{11}{4}W$ colors, where W denotes the weighted clique number. Next, we present a polynomial time approximation algorithm which garantees at most 2W colors for multicoloring a power square mesh. Fur…

Automorphism groups of some affine and finite type Artin groups

2004

We observe that, for fixed n ≥ 3, each of the Artin groups of finite type An, Bn = Cn, and affine type ˜ An−1 and ˜ Cn−1 is a central extension of a finite index subgroup of the mapping class group of the (n + 2)-punctured sphere. (The centre is trivial in the affine case and infinite cyclic in the finite type cases). Using results of Ivanov and Korkmaz on abstract commensurators of surface mapping class groups we are able to determine the automorphism groups of each member of these four infinite families of Artin groups. A rank n Coxeter matrix is a symmetric n × n matrix M with integer entries mij ∈ N ∪ {∞} where mij ≥ 2 for ij, and mii = 1 for all 1 ≤ i ≤ n. Given any rank n Coxeter matr…

Three-page encoding and complexity theory for spatial graphs

2004

We construct a series of finitely presented semigroups. The centers of these semigroups encode uniquely up to rigid ambient isotopy in 3-space all non-oriented spatial graphs. This encoding is obtained by using three-page embeddings of graphs into the product of the line with the cone on three points. By exploiting three-page embeddings we introduce the notion of the three-page complexity for spatial graphs. This complexity satisfies the properties of finiteness and additivity under natural operations.

About Graph Unions and Intersections

2020

Summary In this article the union and intersection of a set of graphs are formalized in the Mizar system [5], based on the formalization of graphs in [7].

On Different Type Solutions of Boundary Value Problems

2016

We consider boundary value problems of the type x'' = f(t, x, x'), (∗) x(a) = A, x(b) = B. A solution ξ(t) of the above BVP is said to be of type i if a solution y(t) of the respective equation of variations y'' = fx(t, ξ(t), ξ' (t))y + fx' (t, ξ(t), ξ' (t))y' , y(a) = 0, y' (a) = 1, has exactly i zeros in the interval (a, b) and y(b) 6= 0. Suppose there exist two solutions x1(t) and x2(t) of the BVP. We study properties of the set S of all solutions x(t) of the equation (∗) such that x(a) = A, x'1(a) ≤ x' (a) ≤ x'2(a) provided that solutions extend to the interval [a, b].

Counterexamples to the Algebraic Closed Graph Theorem

1982

Scaling theory for radial distributions of star polymers in dilute solution in the bulk and at a surface, and scaling of polymer networks near the ad…

1991

Monomer density profiles ρ(r) and center–end distribution functions g(rCE) of star polymers are analyzed by using a scaling theory in arbitrary dimensions d, considering dilute solutions and the good solvent limit. Both the case of a free star in the bulk and of a center‐adsorbed star at a free surface are considered. In the latter case of a semi‐infinite problem, a distinction is made between repulsive walls, attractive walls—where for large arm length l the configuration of the star is quasi‐(d−1) dimensional—, and ‘‘marginal walls’’ where for l→∞ the transition from d‐dimensional structure occurs. For free stars, ρ(r) behaves as r−d+1/ν for small r, where ν is the exponent describing the…

Monte Carlo simulation of many-arm star polymers in two-dimensional good solvents in the bulk and at a surface

1991

A Monte Carlo technique is proposed for the simulation of statistical properties of many-arm star polymers on lattices. In this vectorizing algorithm, the length of each arml is increased by one, step by step, from a starting configuration withl=1 orl=2 which is generated directly. This procedure is carried out for a large sample (e.g., 100,000 configurations). As an application, we have studied self-avoiding stars on the square lattice with arm lengths up tol max=125 and up tof=20 arms, both in the bulk and in the geometry where the center of the star is adsorbed on a repulsive surface. The total number of configurations, which behaves asN∼l γ G–1μ fl , whereμ=2.6386 is the usual effective…

Longest Common Subsequence from Fragments via Sparse Dynamic Programming

1998

Sparse Dynamic Programming has emerged as an essential tool for the design of efficient algorithms for optimization problems coming from such diverse areas as Computer Science, Computational Biology and Speech Recognition [7,11,15]. We provide a new Sparse Dynamic Programming technique that extends the Hunt-Szymanski [2,9,8] paradigm for the computation of the Longest Common Subsequence (LCS) and apply it to solve the LCS from Fragments problem: given a pair of strings X and Y (of length n and m, resp.) and a set M of matching substrings of X and Y, find the longest common subsequence based only on the symbol correspondences induced by the substrings. This problem arises in an application t…