53
53

Sep 22, 2013
09/13

by
V. C. Barbosa

texts

#
eye 53

#
favorite 0

#
comment 0

We discuss general models of resource-sharing computations, with emphasis on the combinatorial structures and concepts that underlie the various deadlock models that have been proposed, the design of algorithms and deadlock-handling policies, and concurrency issues. These structures are mostly graph-theoretic in nature, or partially ordered sets for the establishment of priorities among processes and acquisition orders on resources. We also discuss graph-coloring concepts as they relate to...

Source: http://arxiv.org/abs/cs/0309044v1

40
40

Sep 22, 2013
09/13

by
V. C. Barbosa

texts

#
eye 40

#
favorite 0

#
comment 0

For $k\ge 1$, we consider interleaved $k$-tuple colorings of the nodes of a graph, that is, assignments of $k$ distinct natural numbers to each node in such a way that nodes that are connected by an edge receive numbers that are strictly alternating between them with respect to the relation $

Source: http://arxiv.org/abs/math/0309380v1

67
67

Sep 23, 2013
09/13

by
A. O. Stauffer; V. C. Barbosa

texts

#
eye 67

#
favorite 0

#
comment 0

We study the use of local heuristics to determine spanning subgraphs for use in the dissemination of information in complex networks. We introduce two different heuristics and analyze their behavior in giving rise to spanning subgraphs that perform well in terms of allowing every node of the network to be reached, of requiring relatively few messages and small node bandwidth for information dissemination, and also of stretching paths with respect to the underlying network only modestly. We...

Source: http://arxiv.org/abs/cs/0411090v1

47
47

Sep 22, 2013
09/13

by
L. D. Penso; V. C. Barbosa

texts

#
eye 47

#
favorite 0

#
comment 0

We consider a connected undirected graph $G(n,m)$ with $n$ nodes and $m$ edges. A $k$-dominating set $D$ in $G$ is a set of nodes having the property that every node in $G$ is at most $k$ edges away from at least one node in $D$. Finding a $k$-dominating set of minimum size is NP-hard. We give a new synchronous distributed algorithm to find a $k$-dominating set in $G$ of size no greater than $\lfloor n/(k+1)\rfloor$. Our algorithm requires $O(k\log^*n)$ time and $O(m\log k+n\log k\log^*n)$...

Source: http://arxiv.org/abs/cs/0309040v1

44
44

Sep 22, 2013
09/13

by
A. O. Stauffer; V. C. Barbosa

texts

#
eye 44

#
favorite 0

#
comment 0

We study the problem of disseminating a piece of information through all the nodes of a network, given that it is known originally only to a single node. In the absence of any structural knowledge on the network other than the nodes' neighborhoods, this problem is traditionally solved by flooding all the network's edges. We analyze a recently introduced probabilistic algorithm for flooding and give an alternative probabilistic heuristic that can lead to some cost-effective improvements, like...

Source: http://arxiv.org/abs/cs/0409001v1

54
54

Sep 22, 2013
09/13

by
V. C. Barbosa; R. G. Ferreira

texts

#
eye 54

#
favorite 0

#
comment 0

We study combinatorial indicators related to the characteristic phase transitions associated with coloring a graph optimally and finding a maximum independent set. In particular, we investigate the role of the acyclic orientations of the graph in the hardness of finding the graph's chromatic number and independence number. We provide empirical evidence that, along a sequence of increasingly denser random graphs, the fraction of acyclic orientations that are `shortest' peaks when the chromatic...

Source: http://arxiv.org/abs/cond-mat/0309518v1

41
41

Sep 18, 2013
09/13

by
A. H. L. Porto; V. C. Barbosa

texts

#
eye 41

#
favorite 0

#
comment 0

We introduce a new methodology for the determination of amino-acid substitution matrices for use in the alignment of proteins. The new methodology is based on a pre-existing set cover on the set of residues and on the undirected graph that describes residue exchangeability given the set cover. For fixed functional forms indicating how to obtain edge weights from the set cover and, after that, substitution-matrix elements from weighted distances on the graph, the resulting substitution matrix...

Source: http://arxiv.org/abs/q-bio/0504007v1

61
61

Sep 22, 2013
09/13

by
V. C. Barbosa; L. C. D. Campos

texts

#
eye 61

#
favorite 0

#
comment 0

We introduce a novel evolutionary formulation of the problem of finding a maximum independent set of a graph. The new formulation is based on the relationship that exists between a graph's independence number and its acyclic orientations. It views such orientations as individuals and evolves them with the aid of evolutionary operators that are very heavily based on the structure of the graph and its acyclic orientations. The resulting heuristic has been tested on some of the Second DIMACS...

Source: http://arxiv.org/abs/cs/0309038v1

52
52

Sep 24, 2013
09/13

by
A. H. L. Porto; V. C. Barbosa

texts

#
eye 52

#
favorite 0

#
comment 0

We introduce a new heuristic for the multiple alignment of a set of sequences. The heuristic is based on a set cover of the residue alphabet of the sequences, and also on the determination of a significant set of blocks comprising subsequences of the sequences to be aligned. These blocks are obtained with the aid of a new data structure, called a suffix-set tree, which is constructed from the input sequences with the guidance of the residue-alphabet set cover and generalizes the well-known...

Source: http://arxiv.org/abs/q-bio/0412021v1

55
55

Sep 22, 2013
09/13

by
A. H. L. Porto; V. C. Barbosa

texts

#
eye 55

#
favorite 0

#
comment 0

We introduce a novel definition of approximate palindromes in strings, and provide an algorithm to find all maximal approximate palindromes in a string with up to $k$ errors. Our definition is based on the usual edit operations of approximate pattern matching, and the algorithm we give, for a string of size $n$ on a fixed alphabet, runs in $O(k^2 n)$ time. We also discuss two implementation-related improvements to the algorithm, and demonstrate their efficacy in practice by means of both...

Source: http://arxiv.org/abs/cs/0309043v1

60
60

Sep 22, 2013
09/13

by
L. M. A. Drummond; V. C. Barbosa

texts

#
eye 60

#
favorite 0

#
comment 0

Matrix clocks are a generalization of the notion of vector clocks that allows the local representation of causal precedence to reach into an asynchronous distributed computation's past with depth $x$, where $x\ge 1$ is an integer. Maintaining matrix clocks correctly in a system of $n$ nodes requires that everymessage be accompanied by $O(n^x)$ numbers, which reflects an exponential dependency of the complexity of matrix clocks upon the desired depth $x$. We introduce a novel type of matrix...

Source: http://arxiv.org/abs/cs/0309042v1

8
8.0

Jul 21, 2022
07/22

by
Karlla V C Barbosa; Thiago V V Costa

texts

#
eye 8

#
favorite 0

#
comment 0

106
106

Sep 22, 2013
09/13

by
V. C. Barbosa; C. A. G. Assis; J. O. do Nascimento

texts

#
eye 106

#
favorite 0

#
comment 0

We introduce two novel evolutionary formulations of the problem of coloring the nodes of a graph. The first formulation is based on the relationship that exists between a graph's chromatic number and its acyclic orientations. It views such orientations as individuals and evolves them with the aid of evolutionary operators that are very heavily based on the structure of the graph and its acyclic orientations. The second formulation, unlike the first one, does not tackle one graph at a time, but...

Source: http://arxiv.org/abs/cs/0309039v1

45
45

Sep 23, 2013
09/13

by
V. C. Barbosa; F. M. N. Miranda; M. C. M. Agostini

texts

#
eye 45

#
favorite 0

#
comment 0

We study the classification of cellular-automaton update rules into Wolfram's four classes. We start with the notion of the input entropy of a spatiotemporal block in the evolution of a cellular automaton, and build on it by introducing two novel entropy measures, one that is also based on inputs to the cells, the other based on state transitions by the cells. Our two new entropies are both targeted at the classification of update rules by parallel machines, being therefore mindful of the...

Source: http://arxiv.org/abs/nlin/0408014v1

46
46

Sep 23, 2013
09/13

by
C. A. G. Assis; E. S. T. Fernandes; V. C. Barbosa

texts

#
eye 46

#
favorite 0

#
comment 0

When a program is loaded into memory for execution, the relative position of its basic blocks is crucial, since loading basic blocks that are unlikely to be executed first places them high in the instruction-memory hierarchy only to be dislodged as the execution goes on. In this paper we study the use of Bayesian networks as models of the input history of a program. The main point is the creation of a probabilistic model that persists as the program is run on different inputs and at each new...

Source: http://arxiv.org/abs/cs/0411080v1

41
41

Sep 22, 2013
09/13

by
F. P. M. Santos; V. C. Barbosa; R. Donanelo; S. R. Souza

texts

#
eye 41

#
favorite 0

#
comment 0

The breakup of glass and alumina plates due to planar impacts on one of their lateral sides is studied. Particular attention is given to investigating the spatial location of the cracks within the plates. Analysis based on a phenomenological model suggests that bifurcations along the cracks' paths are more likely to take place closer to the impact region than far away from it, i. e., the bifurcation probability seems to lower as the perpendicular distance from the impacted lateral in- creases....

Source: http://arxiv.org/abs/1103.4589v1

75
75

Sep 22, 2013
09/13

by
L. E. Flores; E. J. Aguilar; V. C. Barbosa; L. A. V. de Carvalho

texts

#
eye 75

#
favorite 0

#
comment 0

The immune system protects the body against health-threatening entities, known as antigens, through very complex interactions involving the antigens and the system's own entities. One remarkable feature resulting from such interactions is the immune system's ability to improve its capability to fight antigens commonly found in the individual's environment. This adaptation process is called the evolution of specificity. In this paper, we introduce a new mathematical model for the evolution of...

Source: http://arxiv.org/abs/q-bio/0310030v1