Página 1 dos resultados de 4829 itens digitais encontrados em 0.045 segundos

## Caminhos mais longos em grafos; Longest paths in graphs

De Rezende, Susanna Figueiredo
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Relevância na Pesquisa
45.79%
O tema central deste trabalho é o estudo de problemas sobre caminhos mais longos em grafos, de pontos de vista tanto estrutural como algorítmico. A primeira parte tem como foco o estudo de problemas motivados pela seguinte questão levantada por T. Gallai em 1966: é verdade que em todo grafo conexo existe um vértice comum a todos os seus caminhos mais longos? Hoje, já se conhecem diversos grafos conexos cuja intersecção de todos os seus caminhos mais longos é vazia. Entretanto, existem classes de grafos para as quais a resposta à pergunta de Gallai é afirmativa. Nessa linha, apresentamos alguns resultados da literatura e duas novas classes que obtivemos: os grafos exoplanares e as 2-árvores. Motivado por esse problema, nos anos 80, T. Zamfirescu formulou a seguinte pergunta que permanece em aberto: é verdade que em todo grafo conexo existe um vértice comum a quaisquer três de seus caminhos mais longos? Apresentamos, além de alguns resultados conhecidos, uma prova de que a resposta é afirmativa para grafos em que todo bloco não trivial é hamiltoniano. Notamos que esse último resultado e o acima mencionado para grafos exoplanares generalizam um teorema de M. Axenovich (2009) que afirma que quaisquer três caminhos mais longos em um grafo exoplanar têm um vértice em comum. Finalmente...

## Empacotamento de árvores em grafos completos; Packing trees into complete graphs

Gómez Diaz, Renzo Gonzalo
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Relevância na Pesquisa
36.06%
Nesta dissertacao estudamos problemas de empacotamento de arvores em grafos, com enfase no caso de grafos completos. Denotamos por Ti uma arvore de ordem i. Dizemos que existe um empacotamento de arvores T1, . . . , Tn num grafo G se e possivel encontrar em G subgrafos H1, . . . , Hn, dois a dois disjuntos nas arestas, tais que Hi e isomorfo a Ti. Em 1976, A. Gyarfas e J. Lehel levantaram a seguinte questao, que conjecturaram ter uma resposta positiva: e possivel empaco- tar qualquer sequencia de arvores T1, . . . , Tn no Kn? Esta dissertacao tem como tema principal os estudos realizados por diversos pesquisadores na busca de uma resposta para esta pergunta, que permanece ainda em aberto. Tendo em vista a dificuldade para tratar esta questao, surge natural- mente a pergunta sobre a existencia de classes de arvores para as quais a resposta e afirmativa. Nessa linha, existem diversos resultados positivos, como por exemplo quando queremos empacotar estrelas e caminhos, ou estrelas e biestrelas. Por outro lado, em vez de restringir a classe das arvores, faz sentido restringir o tamanho da sequencia e reformular a pergunta. Por exemplo, dado s < n, e possivel empacotar qualquer sequencia de arvores T1, . . . , Ts no Kn? Em 1983, Bollobas mostrou ? que a resposta e afirmativa se s <= n / sqrt(2). Na primeira parte deste trabalho focamos nosso estudo em questoes desse tipo. Na segunda parte desta dissertacao investigamos algumas conjecturas que foram motivadas pela pergunta levantada por Gyarfas & Lehel. Por exemplo...

## The future of large old trees in urban landscapes

Le Roux, Darren S.; Ikin, Karen; Lindenmayer, David B.; Manning, Adrian D.; Gibbons, Philip
Fonte: Public Library of Science Publicador: Public Library of Science
Tipo: Artigo de Revista Científica Formato: 11 pages
Relevância na Pesquisa
36.04%
Large old trees are disproportionate providers of structural elements (e.g. hollows, coarse woody debris), which are crucial habitat resources for many species. The decline of large old trees in modified landscapes is of global conservation concern. Once large old trees are removed, they are difficult to replace in the short term due to typically prolonged time periods needed for trees to mature (i.e. centuries). Few studies have investigated the decline of large old trees in urban landscapes. Using a simulation model, we predicted the future availability of native hollow-bearing trees (a surrogate for large old trees) in an expanding city in southeastern Australia. In urban greenspace, we predicted that the number of hollow-bearing trees is likely to decline by 87% over 300 years under existing management practices. Under a worst case scenario, hollow-bearing trees may be completely lost within 115 years. Conversely, we predicted that the number of hollow-bearing trees will likely remain stable in semi-natural nature reserves. Sensitivity analysis revealed that the number of hollow-bearing trees perpetuated in urban greenspace over the long term is most sensitive to the: (1) maximum standing life of trees; (2) number of regenerating seedlings ha(-1); and (3) rate of hollow formation. We tested the efficacy of alternative urban management strategies and found that the only way to arrest the decline of large old trees requires a collective management strategy that ensures: (1) trees remain standing for at least 40% longer than currently tolerated lifespans; (2) the number of seedlings established is increased by at least 60%; and (3) the formation of habitat structures provided by large old trees is accelerated by at least 30% (e.g. artificial structures) to compensate for short term deficits in habitat resources. Immediate implementation of these recommendations is needed to avert long term risk to urban biodiversity.; Darren Le Roux was funded by an Australian Postgraduate Award from the Australian National University and a top-up scholarship from the Land Development Agency (ACT Government). The authors also received funding from The Environmental Decision Hub of the Australian Government’s National Environmental Research Program.

## Interacting Factors Driving a Major Loss of Large Trees with Cavities in a Forest Ecosystem

Lindenmayer, David B.; Blanchard, Wade; McBurney, Lachlan; Blair, David; Banks, Sam; Likens, Gene E.; Franklin, Jerry F.; Laurance, William F.; Stein, John A. R.; Gibbons, Philip
Fonte: Public Library of Science Publicador: Public Library of Science
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
35.97%
Large trees with cavities provide critical ecological functions in forests worldwide, including vital nesting and denning resources for many species. However, many ecosystems are experiencing increasingly rapid loss of large trees or a failure to recruit new large trees or both. We quantify this problem in a globally iconic ecosystem in southeastern Australia--forests dominated by the world's tallest angiosperms, Mountain Ash (Eucalyptus regnans). Tree, stand and landscape-level factors influencing the death and collapse of large living cavity trees and the decay and collapse of dead trees with cavities are documented using a suite of long-term datasets gathered between 1983 and 2011. The historical rate of tree mortality on unburned sites between 1997 and 2011 was >14% with a mortality spike in the driest period (2006-2009). Following a major wildfire in 2009, 79% of large living trees with cavities died and 57-100% of large dead trees were destroyed on burned sites. Repeated measurements between 1997 and 2011 revealed no recruitment of any new large trees with cavities on any of our unburned or burned sites. Transition probability matrices of large trees with cavities through increasingly decayed condition states projects a severe shortage of large trees with cavities by 2039 that will continue until at least 2067. This large cavity tree crisis in Mountain Ash forests is a product of: (1) the prolonged time required (>120 years) for initiation of cavities; and (2) repeated past wildfires and widespread logging operations. These latter factors have resulted in all landscapes being dominated by stands ≤72 years and just 1.16% of forest being unburned and unlogged. We discuss how the features that make Mountain Ash forests vulnerable to a decline in large tree abundance are shared with many forest types worldwide.; This work was supported by Australian Research Council DP1097170; Parks Victoria; and Victorian Department of Sustainability and Environment. The funders had no role in study design...

## Enumeration of labeled and unlabeled k-gonal and polygonal 2-trees and succulents by vertices

Gainer-Dewar, Andrew
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
45.78%
We use the theory of \Gamma-species to enumerate k-gonal and polygonal 2-trees with respect to their vertices. We then extend this result to enumerate "succulents", a tree-like class of graphs which generalize cacti.; Comment: 12 pages, 4 figures, 2 tables of enumerative data, includes Sage code

## Arithmetic for Rooted Trees

Luccio, Fabrizio
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
35.97%
We propose a new arithmetic for rooted unordered trees of n vertices and a method for their enumeration. We define three arithmetic operations on trees called addition, addition-plus, and multiplication and show how all trees can be generated by addition and addition-plus from a starting tree proving that both operations are needed. We show how a given tree can be obtained as the sum, sum-plus, or product of two trees, thus defining prime trees with respect to the three operations, and prove that primality can be decided in time polynomial in n. We suggest how these concepts can be useful and discuss the two lines of similar studies appeared in the literature; Comment: 18 pages, 7 figures

## Comparing and Aggregating Partially Resolved Trees

Bansal, Mukul S.; Dong, Jianrong; Fernández-Baca, David
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.03%
We define, analyze, and give efficient algorithms for two kinds of distance measures for rooted and unrooted phylogenies. For rooted trees, our measures are based on the topologies the input trees induce on triplets; that is, on three-element subsets of the set of species. For unrooted trees, the measures are based on quartets (four-element subsets). Triplet and quartet-based distances provide a robust and fine-grained measure of the similarities between trees. The distinguishing feature of our distance measures relative to traditional quartet and triplet distances is their ability to deal cleanly with the presence of unresolved nodes, also called polytomies. For rooted trees, these are nodes with more than two children; for unrooted trees, they are nodes of degree greater than three. Our first class of measures are parametric distances, where there is a parameter that weighs the difference between an unresolved triplet/quartet topology and a resolved one. Our second class of measures are based on Hausdorff distance. Each tree is viewed as a set of all possible ways in which the tree could be refined to eliminate unresolved nodes. The distance between the original (unresolved) trees is then taken to be the Hausdorff distance between the associated sets of fully resolved trees...

## Maintaining Information in Fully-Dynamic Trees with Top Trees

Alstrup, Stephen; Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.05%
We introduce top trees as a design of a new simpler interface for data structures maintaining information in a fully-dynamic forest. We demonstrate how easy and versatile they are to use on a host of different applications. For example, we show how to maintain the diameter, center, and median of each tree in the forest. The forest can be updated by insertion and deletion of edges and by changes to vertex and edge weights. Each update is supported in O(log n) time, where n is the size of the tree(s) involved in the update. Also, we show how to support nearest common ancestor queries and level ancestor queries with respect to arbitrary roots in O(log n) time. Finally, with marked and unmarked vertices, we show how to compute distances to a nearest marked vertex. The later has applications to approximate nearest marked vertex in general graphs, and thereby to static optimization problems over shortest path metrics. Technically speaking, top trees are easily implemented either with Frederickson's topology trees [Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees, SIAM J. Comput. 26 (2) pp. 484-538, 1997] or with Sleator and Tarjan's dynamic trees [A Data Structure for Dynamic Trees. J. Comput. Syst. Sc. 26 (3) pp. 362-391...

## Characterization of Minimum Cycle Basis in Weighted Partial 2-trees

Narayanaswamy, N. S.; Ramakrishna, G.
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
45.75%
For a weighted outerplanar graph, the set of lex short cycles is known to be a minimum cycle basis [Inf. Process. Lett. 110 (2010) 970-974 ]. In this work, we show that the set of lex short cycles is a minimum cycle basis in weighted partial 2-trees (graphs of treewidth two) which is a superclass of outerplanar graphs.; Comment: 6 pages, 5 figures

## Hamiltonian Path in 2-Trees

Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.01%
For a graph, a spanning path is a path containing all vertices and it is also known as \emph{Hamiltonian path}. For general graphs, there is no known necessary and sufficient condition for the existence of Hamiltonian path and the complexity of finding a Hamiltonian path in general graphs is NP-Complete. We present a necessary and sufficient condition for the existence of Hamiltonian path in 2-trees. Using our characterization, we also present a polynomial-time algorithm for the existence of Hamiltonian path in 2-trees. We also highlight the fact that 2-trees are well-known subclass of chordal and planar graphs. This paper makes the first attempt in identifying a non-trivial subclass of planar graphs where Hamiltonian path is polynomial-time solvable which is otherwise NP-Complete on planar as well as chordal graphs. Our characterization is based on a deep understanding of the structure of 2-trees and we believe that the combinatorics presented here can be used in other combinatorial problems restricted to 2-trees.; Comment: 22 pages, 16 figures

## A Characterization of the Degree Sequences of 2-Trees

Bose, Prosenjit; Dujmović, Vida; Krizanc, Danny; Langerman, Stefan; Morin, Pat; Wood, David R.; Wuhrer, Stefanie
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
55.9%
A graph G is a 2-tree if G=K_3, or G has a vertex v of degree 2, whose neighbours are adjacent, and G\v{i}s a 2-tree. A characterization of the degree sequences of 2-trees is given. This characterization yields a linear-time algorithm for recognizing and realizing degree sequences of 2-trees.; Comment: 17 pages, 5 figures

## Spanning Tree Enumeration in 2-trees: Sequential and Parallel Perspective

C, Vandhana.; Bindhu, S. Hima; Renjith, P.; Sadagopan, N.; Supraja, B.
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
35.98%
For a connected graph, a vertex separator is a set of vertices whose removal creates at least two components. A vertex separator $S$ is minimal if it contains no other separator as a strict subset and a minimum vertex separator is a minimal vertex separator of least cardinality. A {\em clique} is a set of mutually adjacent vertices. A 2-tree is a connected graph in which every maximal clique is of size three and every minimal vertex separator is of size two. A spanning tree of a graph $G$ is a connected and an acyclic subgraph of $G$. In this paper, we focus our attention on two enumeration problems, both from sequential and parallel perspective. In particular, we consider listing all possible spanning trees of a 2-tree and listing all perfect elimination orderings of a chordal graph. As far as enumeration of spanning trees is concerned, our approach is incremental in nature and towards this end, we work with the construction order of the 2-tree, i.e. enumeration of $n$-vertex trees are from $n-1$ vertex trees, $n \geq 4$. Further, we also present a parallel algorithm for spanning tree enumeration using $O(2^n)$ processors. To our knowledge, this paper makes the first attempt in designing a parallel algorithm for this problem. We conclude this paper by presenting a sequential and parallel algorithm for enumerating all Perfect Elimination Orderings of a chordal graph.; Comment: 9 pages...

## An Even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings

Kao, Ming-Yang; Lam, Tak-Wah; Sung, Wing-Kin; Ting, Hing-Fung
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36%
A widely used method for determining the similarity of two labeled trees is to compute a maximum agreement subtree of the two trees. Previous work on this similarity measure is only concerned with the comparison of labeled trees of two special kinds, namely, uniformly labeled trees (i.e., trees with all their nodes labeled by the same symbol) and evolutionary trees (i.e., leaf-labeled trees with distinct symbols for distinct leaves). This paper presents an algorithm for comparing trees that are labeled in an arbitrary manner. In addition to this generality, this algorithm is faster than the previous algorithms. Another contribution of this paper is on maximum weight bipartite matchings. We show how to speed up the best known matching algorithms when the input graphs are node-unbalanced or weight-unbalanced. Based on these enhancements, we obtain an efficient algorithm for a new matching problem called the hierarchical bipartite matching problem, which is at the core of our maximum agreement subtree algorithm.; Comment: To appear in Journal of Algorithms

## Tree Contractions and Evolutionary Trees

Kao, Ming-Yang
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.01%
An evolutionary tree is a rooted tree where each internal vertex has at least two children and where the leaves are labeled with distinct symbols representing species. Evolutionary trees are useful for modeling the evolutionary history of species. An agreement subtree of two evolutionary trees is an evolutionary tree which is also a topological subtree of the two given trees. We give an algorithm to determine the largest possible number of leaves in any agreement subtree of two trees T_1 and T_2 with n leaves each. If the maximum degree d of these trees is bounded by a constant, the time complexity is O(n log^2(n)) and is within a log(n) factor of optimal. For general d, this algorithm runs in O(n d^2 log(d) log^2(n)) time or alternatively in O(n d sqrt(d) log^3(n)) time.

## On Minimum Average Stretch Spanning Trees in Polygonal 2-trees

Narayanaswamy, N. S.; Ramakrishna, G.
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
45.94%
A spanning tree of an unweighted graph is a minimum average stretch spanning tree if it minimizes the ratio of sum of the distances in the tree between the end vertices of the graph edges and the number of graph edges. We consider the problem of computing a minimum average stretch spanning tree in polygonal 2-trees, a super class of 2-connected outerplanar graphs. For a polygonal 2-tree on $n$ vertices, we present an algorithm to compute a minimum average stretch spanning tree in $O(n \log n)$ time. This algorithm also finds a minimum fundamental cycle basis in polygonal 2-trees.; Comment: 17 pages, 12 figures

## Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time

Doerr, Carola; Ramakrishna, G.; Schmidt, Jens M.
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
45.86%
We present a linear time algorithm for computing an implicit linear space representation of a minimum cycle basis (MCB) in weighted partial 2-trees, i.e., graphs of treewidth two. The implicit representation can be made explicit in a running time that is proportional to the size of the MCB. Our algorithm improves the result of Borradaile, Sankowski, and Wulff-Nilsen [Min $st$-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time, FOCS 2010]---which computes for all planar graphs an implicit $O(n \log n)$ space representation of an MCB in $O(n \log^5 n)$ time---by a polylog factor for the special case of partial 2-trees. Such an improvement was achieved previously only for outerplanar graphs [Liu and Lu: Minimum Cycle Bases of Weighted Outerplanar Graphs, IPL 110:970--974, 2010].; Comment: major revision of the paper

## A 3-factor approximation algorithm for a Minimum Acyclic Agreement Forest on k rooted, binary phylogenetic trees

Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36%
Phylogenetic trees are leaf-labelled trees, where the leaves correspond to extant species (taxa), and the internal vertices represent ancestral species. The evolutionary history of a set of species can be explained by more than one phylogenetic tree, giving rise to the problem of comparing phylogenetic trees for similarity. Various distance metrics, like the subtree prune-and-regraft (SPR), tree bisection reconnection (TBR) and nearest neighbour interchange (NNI) have been proposed to capture this similarity. The distance between two phylogenetic trees can also be measured by the size of a Maximum Agreement Forest (MAF) on these trees, as it has been shown that the rooted subtree prune-and-regraft distance is 1 less than the size of a MAF. Since computing a MAF of minimum size is an NP-hard problem, approximation algorithms are of interest. Recently, it has been shown that the MAF on k(>=2) trees can be approximated to within a factor of 8. In this paper, we improve this ratio to 3. For certain species, however, the evolutionary history is not completely tree-like. Due to reticulate evolution two gene trees, though related, appear different, making a phylogenetic network a more appropriate representation of reticulate evolution. A phylogenetic network contains hybrid nodes for the species evolved from two parents. The number of such nodes is its hybridization number. It has been shown that this number is 1 less than the size of a Maximum Acyclic Agreement Forest (MAAF). We show that the MAAF for k(>= 2) phylogenetic trees can be approximated to within a factor of 3.; Comment: 14 pages...

## Labelled and unlabelled enumeration of $k$-gonal 2-trees

Labelle, G.; Lamathe, C.; Leroux, P.
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
45.93%
In this paper, we generalize 2-trees by replacing triangles by quadrilaterals, pentagons or $k$-sided polygons ($k$-gons), where $k\geq 3$ is fixed. This generalization, to $k$-gonal 2-trees, is natural and is closely related, in the planar case, to some specializations of the cell-growth problem. Our goal is the labelled and unlabelled enumeration of $k$-gonal 2-trees according to the number $n$ of $k$-gons. We give explicit formulas in the labelled case, and, in the unlabelled case, recursive and asymptotic formulas.; Comment: This is the full version of a paper presented at the second Mathematics and Computer Science Conference in Versailles, France, in September 2002, in "Mathematics and Computer Science II", B. Chauvin, P. Flajolet, D. Gardy and A. Mokkadem, Editors, Trends in Mathematics, Birkhauser Verlag, Basel Switzwerland, 2002, 95--109

## A classification of plane and planar 2-trees

Labelle, G.; Lamathe, C.; Leroux, P.
Tipo: Artigo de Revista Científica