Search results for "Application"
showing 10 items of 5559 documents
On Coloring Unit Disk Graphs
1998
In this paper the coloring problem for unit disk (UD) graphs is considered. UD graphs are the intersection graphs of equal-sized disks in the plane. Colorings of UD graphs arise in the study of channel assignment problems in broadcast networks. Improving on a result of Clark et al. [2] it is shown that the coloring problem for UD graphs remains NP-complete for any fixed number of colors k≥ 3 . Furthermore, a new 3-approximation algorithm for the problem is presented which is based on network flow and matching techniques.
An automata-theoretic approach to the study of the intersection of two submonoids of a free monoid
2008
We investigate the intersection of two finitely generated submonoids of the free monoid on a finite alphabet. To this purpose, we consider automata that recognize such submonoids and we study the product automata recognizing their intersection. By using automata methods we obtain a new proof of a result of Karhumaki on the cha- racterization of the intersection of two submonoids of rank two, in the case of prefix (or suffix) generators. In a more general setting, for an arbitrary number of generators, we prove that if H and K are two finitely generated submonoids generated by prefix sets such that the product automaton associated to H ∩ K has a given special property then �(H ∩ K) ≤ �(H)�(K…
Extensions and intentions in the rough set theory
1998
Abstract The approach to rough set theory proposed in this paper is based on the mutual correspondence of the concepts of extension and intension. It is different from the well-known approaches in the literature in that the upper approximations and the lower approximations of ‘unknown’ sets are considered as certain families of ‘known’ sets. This approach makes it possible to formulate necessary and sufficient conditions for the existence of operations on rough sets, which are analogous to classical operations on sets. The basic results presented in this paper, based on certain ideas of the second author, were formulated by the first author in his doctoral dissertation prepared under the su…
On a pair of fuzzy $\varphi$-contractive mappings
2010
We establish common fixed point theorems for fuzzy mappings under a $\varphi$-contraction condition on a metric space with the d_$\infty$-metric (induced by the Hausdorff metric) on the family of fuzzy sets. The study of fixed points of fuzzy set-valued mappings related to the d_$\infty$-metric is useful in geometric problems arising in high energy physics. Our results generalize some recent results.
The small-world of 'Le Petit Prince': Revisiting the word frequency distribution
2016
[EN] Many complex systems are naturally described through graph theory, and different kinds of systems described as networks present certain important characteristics in common. One of these features is the so-called scale-free distribution for its node s connectivity, which means that the degree distribution for the network s nodes follows a power law. Scale-free networks are usually referred to as small-world because the average distance between their nodes do not scale linearly with the size of the network, but logarithmically. Here we present a mathematical analysis on linguistics: the word frequency effect for different translations of the Le Petit Prince in different languages. Compar…
A class of label-correcting methods for the K shortest paths problem
2001
In this paper we deal with the problem of finding the first K shortest paths from a single origin node to all other nodes of a directed graph. In particular, we define the necessary and sufficient conditions for a set of distance label vectors, on the basis of which we propose a class of methods which can be viewed as an extension of the generic label-correcting method for solving the classical single-origin all-destinations shortest path problem. The data structure used is characterized by a set of K lists of candidate nodes, and the proposed methods differ in the strategy used to select the node to be extracted at each iteration. The computational results show that: 1. some label-correct…
Matchings in three Catalan lattices
2003
In this note we consider a series of lattices that are enumerated by the well-known Catalan numbers. For each of these lattices, we exhibit a matching in a constructive way.
Generating binary trees by Glivenko classes on Tamari lattices
2003
Using algebraic-theoretic results, we give an algorithm for generating binary trees within Glivenko classes in Tamari lattices. Tamari lattices are lattices of binary trees endowed by the well-known rotation transformation.
A-Codes from Rational Functions over Galois Rings
2006
In this paper, we describe authentication codes via (generalized) Gray images of suitable codes over Galois rings. Exponential sums over these rings help determine--or bound--the parameters of such codes.
Hopcroft's algorithm and tree-like automata
2011
Minimizing a deterministic finite automata (DFA) is a very important problem in theory of automata and formal languages. Hopcroft's algorithm represents the fastest known solution to the such a problem. In this paper we analyze the behavior of this algorithm on a family binary automata, called tree-like automata, associated to binary labeled trees constructed by words. We prove that all the executions of the algorithm on tree-like automata associated to trees, constructed by standard words, have running time with the same asymptotic growth rate. In particular, we provide a lower and upper bound for the running time of the algorithm expressed in terms of combinatorial properties of the trees…