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

Fonte: ELSEVIER SCIENCE BV
Publicador: ELSEVIER SCIENCE BV

Tipo: Artigo de Revista Científica

ENG

Relevância na Pesquisa

66.24%

#Elevated plus-maze#Rat exploratory behavior#Directed graph#Anxiety#ANXIETY-LIKE BEHAVIOR#MODEL#VALIDATION#Biochemical Research Methods#Neurosciences

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

Link permanente para citações:

## The Jordan canonical form for a class of weighted directed graphs

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.

Link permanente para citações:

## Directed Graph Based Image Registration

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...

Link permanente para citações:

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

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.

Link permanente para citações:

## A construction for the hat problem on a directed graph

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

Link permanente para citações:

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

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.

Link permanente para citações:

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

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.

Link permanente para citações:

## An Alternative Construction to the Transitive Closure of a Directed Graph

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

Link permanente para citações:

## Stochastic dynamics of model proteins on a directed graph

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...

Link permanente para citações:

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

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.

Link permanente para citações:

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

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)

Link permanente para citações:

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

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

Link permanente para citações:

## Simple and Faster algorithm for Reachability in a Decremental Directed Graph

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$)...

Link permanente para citações:

## Nest representations of directed graph algebras

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

Link permanente para citações:

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

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.

Link permanente para citações:

## The number of Euler tours of a random directed graph

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 09/02/2012

Relevância na Pesquisa

46.3%

#Computer Science - Discrete Mathematics#Computer Science - Data Structures and Algorithms#Mathematics - Combinatorics#Mathematics - Probability#05C45, 05C80, 68R05

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.

Link permanente para citações:

## Some new classes of directed graph IFSs

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

Link permanente para citações:

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

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

Link permanente para citações:

## On uniform sampling simple directed graph realizations of degree sequences

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

Link permanente para citações:

## Directed hyper-graphs for RDF documents

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

Link permanente para citações: