Página 1 dos resultados de 1993 itens digitais encontrados em 0.013 segundos

Characterization of rat behavior in the elevated plus-maze using a directed graph

TEJADA, Julian; BOSCO, Geraldine G.; MORATO, Silvio; ROQUE, Antonio C.
Fonte: ELSEVIER SCIENCE BV Publicador: ELSEVIER SCIENCE BV
Tipo: Artigo de Revista Científica
ENG
Relevância na Pesquisa
66.24%
The elevated plus-maze is a device widely used to assess rodent anxiety under the effect of several treatments, including pharmacological agents. The animal is placed at the center of the apparatus, which consists of two open arms and two arms enclosed by walls, and the number of entries and duration of stay in each arm are measured for a 5-min exposure period. The effect of an anxiolytic drug is to increase the percentage of time spent and number of entries into the open arms. In this work, we propose a new measure of anxiety levels in the rat submitted to the elevated plus-maze. We represented the spatial structure of the elevated plus-maze in terms of a directed graph and studied the statistics of the rat`s transitions between the nodes of the graph. By counting the number of times each transition is made and ordering them in descending frequency we represented the rat`s behavior in a rank-frequency plot. Our results suggest that the curves obtained under different pharmacological conditions can be well fitted by a power law with an exponent sensitive to both the drug type and the dose used. (C) 2009 Elsevier B.V. All rights reserved.; FAPESP; CNPq

The Jordan canonical form for a class of weighted directed graphs

Nina, H.; Soto, R. L.; Cardoso, D. M.
Fonte: Elsevier Publicador: Elsevier
Tipo: Artigo de Revista Científica
ENG
Relevância na Pesquisa
56.23%
Recently, Cardon and Tuckfield (2011) [1] have described the Jordan canonical form for a class of zero-one matrices, in terms of its associated directed graph. In this paper, we generalize this result to describe the Jordan canonical form of a weighted adjacency matrix A in terms of its weighted directed graph.

Directed Graph Based Image Registration

Jia, Hongjun; Wu, Guorong; Wang, Qian; Wang, Yaping; Kim, Minjeong; Shen, Dinggang
Fonte: PubMed Publicador: PubMed
Tipo: Artigo de Revista Científica
EN
Relevância na Pesquisa
46.45%
In this paper, a novel image registration method is proposed to achieve accurate registration between images having large shape differences with the help of a set of appropriate intermediate templates. We first demonstrate that directionality is a key factor in both pairwise image registration and groupwise registration, which is defined in this paper to describe the influence of the registration direction and paths on the registration performance. In our solution, the intermediate template selection and intermediate template guided registration are two coherent steps with directionality being considered. To take advantage of the directionality, a directed graph is built based on the asymmetric distance defined on all ordered image pairs in the image population, which is fundamentally different from the undirected graph with symmetric distance metrics in all previous methods, and the shortest distance between template and subject on the directed graph is calculated. The allocated directed path can be thus utilized to better guide the registration by successively registering the subject through the intermediate templates one by one on the path towards the template. The proposed directed graph based solution can also be used in groupwise registration. Specifically...

Valid Inequalities and Facets for the Steinger Problem in a Directed Graph

Myung, Young-soo
Fonte: Massachusetts Institute of Technology, Operations Research Center Publicador: Massachusetts Institute of Technology, Operations Research Center
Tipo: Trabalho em Andamento Formato: 1159153 bytes; application/pdf
EN_US
Relevância na Pesquisa
66.19%
In this paper, we describe the facial structure of the steiner problem in a directed graph by formulating it as a set covering problem. We first characterize trivial facets and derive a necessary condition for nontrivial facets. We also introduce a class of valid inequalities with 0-1 coefficients and show when such inequalities define facets.

A construction for the hat problem on a directed graph

Hod, Rani; Krzywkowski, Marcin
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.28%
A team of players plays the following game. After a strategy session, each player is randomly fitted with a blue or red hat. Then, without further communication, everybody can try to guess simultaneously his or her own hat color by looking at the hat colors of other players. Visibility is defined by a directed graph; that is, vertices correspond to players, and a player can see each player to whom she or he is connected by an arc. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The team aims to maximize the probability of a win, and this maximum is called the hat number of the graph. Previous works focused on the problem on complete graphs and on undirected graphs. Some cases were solved, e.g., complete graphs of certain orders, trees, cycles, bipartite graphs. These led Uriel Feige to conjecture that the hat number of any graph is equal to the hat number of its maximum clique. We show that the conjecture does not hold for directed graphs.Moreover, for every value of the maximum clique size, we provide a tight characterization of the range of possible values of the hat number. We construct families of directed graphs with a fixed clique number the hat number of which is asymptotically optimal. We also determine the hat number of tournaments to be one half.; Comment: 9 pages. v2: updated title and abstract to match journal version

Attractors of directed graph IFSs that are not standard IFS attractors and their Hausdorff measure

Boore, G. C.; Falconer, K. J.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 11/08/2011
Relevância na Pesquisa
46.28%
For directed graph iterated function systems (IFSs) defined on R, we prove that a class of 2-vertex directed graph IFSs have attractors that cannot be the attractors of standard (1-vertex directed graph) IFSs, with or without separation conditions. We also calculate their exact Hausdorff measure. Thus we are able to identify a new class of attractors for which the exact Hausdorff measure is known.

A sufficient condition for the existence of an anti-directed 2-factor in a directed graph

Diwan, Ajit A.; Frye, Josh B.; Plantholt, Michael J.; Tipnis, Shailesh K.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.39%
Let D be a directed graph with vertex set V and order n. An anti-directed hamiltonian cycle H in D is a hamiltonian cycle in the graph underlying D such that no pair of consecutive arcs in H form a directed path in D. An anti-directed 2-factor in D is a vertex-disjoint collection of anti-directed cycles in D that span V. It was proved in [3] that if the indegree and the outdegree of each vertex of D is greater than (9/16)n then D contains an anti-directed hamilton cycle. In this paper we prove that given a directed graph D, the problem of determining whether D has an anti-directed 2-factor is NP-complete, and we use a proof technique similar to the one used in [3] to prove that if the indegree and the outdegree of each vertex of D is greater than (24/46)n then D contains an anti-directed 2-factor.

An Alternative Construction to the Transitive Closure of a Directed Graph

Price, Kenneth L.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.31%
One must add arrows which are forced by transitivity to form the transitive closure of a directed graph. We introduce a construction of a transitive directed graph which is formed by adding vertices instead of arrows and which preserves the transitive relationships formed by distinct vertices in the original directed graph. Our construction does not apply to all directed graphs.; Comment: 4 figures

Stochastic dynamics of model proteins on a directed graph

Bongini, L.; Casetti, L.; Livi, R.; Politi, A.; Torcini, A.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 19/11/2008
Relevância na Pesquisa
46.36%
A method for reconstructing the energy landscape of simple polypeptidic chains is described. We show that we can construct an equivalent representation of the energy landscape by a suitable directed graph. Its topological and dynamical features are shown to yield an effective estimate of the time scales associated with the folding and with the equilibration processes. This conclusion is drawn by comparing molecular dynamics simulations at constant temperature with the dynamics on the graph, defined by a temperature dependent Markov process. The main advantage of the graph representation is that its dynamics can be naturally renormalized by collecting nodes into "hubs", while redefining their connectivity. We show that both topological and dynamical properties are preserved by the renormalization procedure. Moreover, we obtain clear indications that the heteropolymers exhibit common topological properties, at variance with the homopolymer, whose peculiar graph structure stems from its spatial homogeneity. In order to obtain a clear distinction between a "fast folder" and a "slow folder" in the heteropolymers one has to look at kinetic features of the directed graph. We find that the average time needed to the fast folder for reaching its native configuration is two orders of magnitude smaller than its equilibration time...

Analysis of d-Hop Dominating Set Problem for Directed Graph with Indegree Bounded by One

Banerjee, Joydeep; Das, Arun; Sen, Arunabha
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 28/04/2014
Relevância na Pesquisa
46.24%
d-hop dominating set problem was introduced for cluster formation in wireless ad-hoc networks and is proved to be NP-complete. Dominating set problem for directed graph with indegree of at most 1 can be solved polynomially. In this article we perform an analysis of d-hop dominating set problem for directed graph with indegree 1. We show that the problem can be solved polynomially by exploiting certain properties of the graph under consideration.

Directed Graph Representation of Half-Rate Additive Codes over GF(4)

Danielsen, Lars Eirik; Parker, Matthew G.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.19%
We show that (n,2^n) additive codes over GF(4) can be represented as directed graphs. This generalizes earlier results on self-dual additive codes over GF(4), which correspond to undirected graphs. Graph representation reduces the complexity of code classification, and enables us to classify additive (n,2^n) codes over GF(4) of length up to 7. From this we also derive classifications of isodual and formally self-dual codes. We introduce new constructions of circulant and bordered circulant directed graph codes, and show that these codes will always be isodual. A computer search of all such codes of length up to 26 reveals that these constructions produce many codes of high minimum distance. In particular, we find new near-extremal formally self-dual codes of length 11 and 13, and isodual codes of length 24, 25, and 26 with better minimum distance than the best known self-dual codes.; Comment: Presented at International Workshop on Coding and Cryptography (WCC 2009), 10-15 May 2009, Ullensvang, Norway. (14 pages, 2 figures)

A family of partitions of the set of walks on a directed graph

Thwaite, Simon
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.19%
We present a family of partitions of $W_\mathcal{G}$, the set of walks on a directed graph $\mathcal{G}$. Each partition in this family is identified by an integer sequence $K$, which specifies a collection of cycles on $\mathcal{G}$ with a certain well-defined structure. We term such cycles resummable, and a walk that does not traverse any such cycles $K$-irreducible. For a given value of $K$, the corresponding partition of $W_\mathcal{G}$ consists of a collection of cells that each contain a single $K$-irreducible walk $i$ plus all walks that can be formed from $i$ by attaching one or more resummable cycles to its vertices. We characterise the entire family of partitions of $W_\mathcal{G}$ by giving explicit expressions for the structure of the $K$-irreducible walks and the resummable cycles for arbitrary values of $K$. We demonstrate how these results can be exploited to recast the sum over all walks on a directed graph as a sum over dressed $K$-irreducible walks, and discuss the applications of this reformulation to matrix computations.; Comment: 55 pages; significantly restructured and expanded from v1

Simple and Faster algorithm for Reachability in a Decremental Directed Graph

Gupta, Manoj
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.24%
Consider the problem of maintaining source sink reachability($st$-Reachability), single source reachability(SSR) and strongly connected component(SCC) in an edge decremental directed graph. In particular, we design a randomized algorithm that maintains with high probability: 1) $st$-Reachability in $\tilde{O}(mn^{4/5})$ total update time. 2) $st$-Reachability in a total update time of $\tilde{O}(n^{8/3})$ in a dense graph. 3) SSR in a total update time of $\tilde{O}(m n^{9/10})$. 4) SCC in a total update time of $\tilde{O}(m n^{9/10})$. For all the above problems, we improve upon the previous best algorithm (by Henzinger et. al. (STOC 2014)). Our main focus is maintaining $st$-Reachability in an edge decremental directed graph (other problems can be reduced to $st$-Reachability). The classical algorithm of Even and Shiloach (JACM 81) solved this problem in $O(1)$ query time and $O(mn)$ total update time. Recently, Henzinger, Krinninger and Nanongkai (STOC 2014) designed a randomized algorithm which achieves an update time of $\tilde{O}(m n^{0.98})$ and broke the long-standing $O(mn)$ bound of Even and Shiloach. However, they designed four algorithms $A_i (1\le i \le 4)$ such that for graphs having total number of edges between $m_i$ and $m_{i+1}$ ($m_{i+1} > m_i$)...

Nest representations of directed graph algebras

Davidson, Kenneth; Katsoulis, Elias
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.19%
This paper is a comprehensive study of the nest representations for the free semigroupoid algebra $\flgee$ of countable directed graph $G$ as well as its norm-closed counterpart, the tensor algebra $\T^{+}(G)$. We prove that the finite dimensional nest representations separate the points in $\flgee$, and a fortiori, in $\T^{+}(G)$. The irreducible finite dimensional representations separate the points in $\flgee$ if and only if $G$ is transitive in components (which is equivalent to being semisimple). Also the upper triangular nest representations separate points if and only if for every vertex $x \in \V(G)$ supporting a cycle, $x$ also supports at least one loop edge. We also study \textit{faithful} nest representations. We prove that $\flgee$ (or $\T^{+}(G)$) admits a faithful irreducible representation if and only if $G$ is strongly transitive as a directed graph. More generally, we obtain a condition on $G$ which is equivalent to the existence of a faithful nest representation. We also give a condition that determines the existence a faithful nest representation for a maximal type $\bN$ nest.; Comment: accepted version for Proc. Lomdon Math. Soc., minor changes

A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights

Cai, Jin-Yi; Chen, Xi
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 05/08/2010
Relevância na Pesquisa
46.34%
The complexity of graph homomorphism problems has been the subject of intense study. It is a long standing open problem to give a (decidable) complexity dichotomy theorem for the partition function of directed graph homomorphisms. In this paper, we prove a decidable complexity dichotomy theorem for this problem and our theorem applies to all non-negative weighted form of the problem: given any fixed matrix A with non-negative algebraic entries, the partition function Z_A(G) of directed graph homomorphisms from any directed graph G is either tractable in polynomial time or #P-hard, depending on the matrix A. The proof of the dichotomy theorem is combinatorial, but involves the definition of an infinite family of graph homomorphism problems. The proof of its decidability is algebraic using properties of polynomials.

The number of Euler tours of a random directed graph

Creed, Páidí; Cryan, Mary
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 09/02/2012
Relevância na Pesquisa
46.3%
In this paper we obtain the expectation and variance of the number of Euler tours of a random Eulerian directed graph with fixed out-degree sequence. We use this to obtain the asymptotic distribution of the number of Euler tours of a random $d$-in/$d$-out graph and prove a concentration result. We are then able to show that a very simple approach for uniform sampling or approximately counting Euler tours yields algorithms running in expected polynomial time for almost every $d$-in/$d$-out graph. We make use of the BEST theorem of de Bruijn, van Aardenne-Ehrenfest, Smith and Tutte, which shows that the number of Euler tours of an Eulerian directed graph with out-degree sequence $\mathbf{d}$ is the product of the number of arborescences and the term $\frac{1}{n}[\prod_{v \in V}(d_v-1)!]$. Therefore most of our effort is towards estimating the moments of the number of arborescences of a random graph with fixed out-degree sequence.

Some new classes of directed graph IFSs

Boore, Graeme
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.39%
It has been shown that certain 2-vertex directed graph iterated function systems (IFSs), defined on the unit interval and satisfying the convex strong separation condition (CSSC), have attractors whose components are not standard IFS attractors where the standard IFSs may be with or without separation conditions. The proof required the multiplicative rational independence of parameters and the calculation of Hausdorff measure. In this paper we present a proof which does not have either of these requirements and so we identify a whole new class of 2-vertex directed graph IFSs. We extend this result to n-vertex (n>=2, CSSC) directed graph IFSs, defined on the unit interval, with no effective restriction on the form of the associated directed graph, subject only to a condition regarding level-1 gap lengths. We also obtain a second result for n-vertex (n>=2, CSSC) directed graph IFSs, defined on the unit interval, which does require the calculation of Hausdorff measure.; Comment: 35 pages, 9 figures, a comment has been added after the statement of Theorem 1.5 which explains how Theorems 1.4 and 1.5 can be easily modified to allow for reflecting similarities

Eigenvectors for clustering: Unipartite, bipartite, and directed graph cases

Mirzal, Andri; Furukawa, Masashi
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.34%
This paper presents a concise tutorial on spectral clustering for broad spectrum graphs which include unipartite (undirected) graph, bipartite graph, and directed graph. We show how to transform bipartite graph and directed graph into corresponding unipartite graph, therefore allowing a unified treatment to all cases. In bipartite graph, we show that the relaxed solution to the $K$-way co-clustering can be found by computing the left and right eigenvectors of the data matrix. This gives a theoretical basis for $K$-way spectral co-clustering algorithms proposed in the literatures. We also show that solving row and column co-clustering is equivalent to solving row and column clustering separately, thus giving a theoretical support for the claim: ``column clustering implies row clustering and vice versa''. And in the last part, we generalize the Ky Fan theorem---which is the central theorem for explaining spectral clustering---to rectangular complex matrix motivated by the results from bipartite graph analysis.; Comment: 9 pages, no figure, to appear in ICEIE 2010

On uniform sampling simple directed graph realizations of degree sequences

Lamar, M. Drew
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 21/12/2009
Relevância na Pesquisa
46.29%
Choosing a uniformly sampled simple directed graph realization of a degree sequence has many applications, in particular in social networks where self-loops are commonly not allowed. It has been shown in the past that one can perform a Markov chain arc-switching algorithm to sample a simple directed graph uniformly by performing two types of switches: a 2-switch and a directed 3-cycle reorientation. This paper discusses under what circumstances a directed 3-cycle reorientation is required. In particular, the class of degree sequences where this is required is a subclass of the directed 3-cycle anchored degree sequences. An important implication of this result is a reduced Markov chain algorithm that uses only 2-switches.; Comment: 7 pages, 4 figures

Directed hyper-graphs for RDF documents

Martínez-Morales,Amadís Antonio; Vidal,María-Esther
Fonte: Facultad de Ingeniería, Universidad del Zulia Publicador: Facultad de Ingeniería, Universidad del Zulia
Tipo: Artigo de Revista Científica Formato: text/html
Publicado em 01/04/2010 EN
Relevância na Pesquisa
46.31%
Resource Description Framework (RDF) is a W3C proposal to express metadata about resources in the Web. The RDF data model has been formalized using several graph-based representations; each one offers different expressive power and support for the tasks of query answering and semantic reasoning. In this paper, we propose a directed hyper-graph formal model to represent and manage RDF documents efficiently. We have developed algorithms that exploit the properties of the proposed representation, and conducted an experimental study to analyze the space and time savings of our solution with respect to the labeled directed graph representation. Our study has been performed over synthetic and real-world RDF documents, and we could observe that our approach reduces the space required to store an RDF document and speeds up the task of query answering, overcoming the labeled directed graph representation