Inhaltsverzeichnis
Auswahl der wissenschaftlichen Literatur zum Thema „EDGE TEST TREE GRAPH“
Geben Sie eine Quelle nach APA, MLA, Chicago, Harvard und anderen Zitierweisen an
Machen Sie sich mit den Listen der aktuellen Artikel, Bücher, Dissertationen, Berichten und anderer wissenschaftlichen Quellen zum Thema "EDGE TEST TREE GRAPH" bekannt.
Neben jedem Werk im Literaturverzeichnis ist die Option "Zur Bibliographie hinzufügen" verfügbar. Nutzen Sie sie, wird Ihre bibliographische Angabe des gewählten Werkes nach der nötigen Zitierweise (APA, MLA, Harvard, Chicago, Vancouver usw.) automatisch gestaltet.
Sie können auch den vollen Text der wissenschaftlichen Publikation im PDF-Format herunterladen und eine Online-Annotation der Arbeit lesen, wenn die relevanten Parameter in den Metadaten verfügbar sind.
Zeitschriftenartikel zum Thema "EDGE TEST TREE GRAPH"
1
Wei, Yuxuan, Zhinan Gao und Xingyan Lu. „The Complexity of Wheel Graphs with Multiple Edges and Vertices“. Asian Research Journal of Mathematics 19, Nr. 9 (19.06.2023): 1–12. http://dx.doi.org/10.9734/arjom/2023/v19i9694.
Der volle Inhalt der QuelleAnnotation:
In this paper, we focus on calculate the number of spanning trees of the general wheel graphs, which meansthe original wheel graphs adding large amount of vertices and edges. Particularly, we introduce the C-graphand deduce a new equation that computing the spanning trees by removing C-graphs instead of edges.In Addition, we test our results by Kirchhoff’s matrix-tree theorem in some simple cases and provide thetree entropy of the general wheel graphs. Finally, we analyse the relation between the wheel graph anddouble-wheel graphs and propose the idea of calculating the spanning trees of double-wheel graphs.
2
Wu, Yuezhong, Qiang Liu, Rongrong Chen, Changyun Li und Ziran Peng. „A Group Recommendation System of Network Document Resource Based on Knowledge Graph and LSTM in Edge Computing“. Security and Communication Networks 2020 (02.12.2020): 1–11. http://dx.doi.org/10.1155/2020/8843803.
Der volle Inhalt der QuelleAnnotation:
The Internet has become one of the important channels for users to obtain information and knowledge. It is crucial to work out how to acquire personalized requirement of users accurately and effectively from huge amount of network document resources. Group recommendation is an information system for group participation in common activities that meets the common interests of all members in the group. This paper proposes a group recommendation system for network document resource exploration using the knowledge graph and LSTM in edge computing, which can solve the problem of information overload and resource trek effectively. An extensive system test has been carried out in the field of big data application in packaging industry. The experimental results show that the proposed system recommends network document resource more accurately and further improves recommendation quality using the knowledge graph and LSTM in edge computing. Therefore, it can meet the user’s personalized resource need more effectively.
3
Zhong, Shuaihao, Duoqiang Wang, Wei Li, Feng Lu und Hai Jin. „Burner: Recipe Automatic Generation for HPC Container Based on Domain Knowledge Graph“. Wireless Communications and Mobile Computing 2022 (25.05.2022): 1–14. http://dx.doi.org/10.1155/2022/4592428.
Der volle Inhalt der QuelleAnnotation:
As one of the emerging cloud computing technologies, containers are widely used in academia and industry. The cloud computing built by the container in the high performance computing (HPC) center can provide high-quality services to users at the edge. Singularity Definition File and Dockerfile (we refer to such files as recipes) have attracted wide attention due to their encapsulation of the application running environment in a container. However, creating a recipe requires extensive domain knowledge, which is error-prone and time-consuming. Accordingly, more than 34% of Dockerfiles in Github cannot successfully build container images. The crucial points about recipe creation include selecting the entities (base images and packages) and determining their relationships (correct installation order for transitive dependencies). Since the relationships between entities can be expressed accurately and efficiently by the knowledge graph, we introduce knowledge graph to generate high-quality recipes automatically. This paper proposes an automatic recipe generation system named Burner, enabling users with no professional computer background to generate the recipes. We first develop a toolset including a recipe parser and an entity-relationship miner. Our two-phase recipe parsing method can perform abstract syntax tree (AST) parsing more deeply on the recipe file to achieve entity extraction; the parsing success rate (PSR) of the two-phase parsing method is 10.1% higher than the one-phase parsing. Then, we build a knowledge base containing 2,832 entities and 62,614 entity relationships, meeting the needs of typical HPC applications. In the test of image build, the singularity image build success rate reaches 80%. Compared with the ItemCF recommendation method, our recommendation method TB-TFIDF achieves a performance improvement by up to 50.86%.
4
Gilani, S. A. N., M. Awrangjeb und G. Lu. „FUSION OF LIDAR DATA AND MULTISPECTRAL IMAGERY FOR EFFECTIVE BUILDING DETECTION BASED ON GRAPH AND CONNECTED COMPONENT ANALYSIS“. ISPRS - International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences XL-3/W2 (10.03.2015): 65–72. http://dx.doi.org/10.5194/isprsarchives-xl-3-w2-65-2015.
Der volle Inhalt der QuelleAnnotation:
Building detection in complex scenes is a non-trivial exercise due to building shape variability, irregular terrain, shadows, and occlusion by highly dense vegetation. In this research, we present a graph based algorithm, which combines multispectral imagery and airborne LiDAR information to completely delineate the building boundaries in urban and densely vegetated area. In the first phase, LiDAR data is divided into two groups: ground and non-ground data, using ground height from a bare-earth DEM. A mask, known as the primary building mask, is generated from the non-ground LiDAR points where the black region represents the elevated area (buildings and trees), while the white region describes the ground (earth). The second phase begins with the process of Connected Component Analysis (CCA) where the number of objects present in the test scene are identified followed by initial boundary detection and labelling. Additionally, a graph from the connected components is generated, where each black pixel corresponds to a node. An edge of a unit distance is defined between a black pixel and a neighbouring black pixel, if any. An edge does not exist from a black pixel to a neighbouring white pixel, if any. This phenomenon produces a disconnected components graph, where each component represents a prospective building or a dense vegetation (a contiguous block of black pixels from the primary mask). In the third phase, a clustering process clusters the segmented lines, extracted from multispectral imagery, around the graph components, if possible. In the fourth step, NDVI, image entropy, and LiDAR data are utilised to discriminate between vegetation, buildings, and isolated building’s occluded parts. Finally, the initially extracted building boundary is extended pixel-wise using NDVI, entropy, and LiDAR data to completely delineate the building and to maximise the boundary reach towards building edges. The proposed technique is evaluated using two Australian data sets: Aitkenvale and Hervey Bay, for object-based and pixel-based completeness, correctness, and quality. The proposed technique detects buildings larger than 50 m<sup>2</sup> and 10 m<sup>2</sup> in the Aitkenvale site with 100% and 91% accuracy, respectively, while in the Hervey Bay site it performs better with 100% accuracy for buildings larger than 10 m<sup>2</sup> in area.
5
Chimani, Markus, Giuseppe Di Battista, Fabrizio Frati und Karsten Klein. „Advances on Testing C-Planarity of Embedded Flat Clustered Graphs“. International Journal of Foundations of Computer Science 30, Nr. 02 (Februar 2019): 197–230. http://dx.doi.org/10.1142/s0129054119500011.
Der volle Inhalt der QuelleAnnotation:
In this paper, we show a polynomial-time algorithm for testing [Formula: see text]-planarity of embedded flat clustered graphs with at most two vertices per cluster on each face. Our result is based on a reduction to the planar set of spanning trees in topological multigraphs (pssttm) problem, which is defined as follows. Given a (non-planar) topological multigraph [Formula: see text] with [Formula: see text] connected components [Formula: see text], do spanning trees of [Formula: see text] exist such that no two edges in any two spanning trees cross? Kratochvíl et al. [SIAM Journal on Discrete Mathematics, 4(2): 223–244, 1991] proved that the problem is NP-hard even if [Formula: see text]; on the other hand, Di Battista and Frati presented a linear-time algorithm to solve the pssttm problem for the case in which [Formula: see text] is a [Formula: see text]-planar topological multigraph [Journal of Graph Algorithms and Applications, 13(3): 349–378, 2009]. For any embedded flat clustered graph [Formula: see text], an instance [Formula: see text] of the pssttm problem can be constructed in polynomial time such that [Formula: see text] is [Formula: see text]-planar if and only if [Formula: see text] admits a solution. We show that, if [Formula: see text] has at most two vertices per cluster on each face, then it can be tested in polynomial time whether the corresponding instance [Formula: see text] of the pssttm problem is positive or negative. Our strategy for solving the pssttm problem on [Formula: see text] is to repeatedly perform a sequence of tests, which might let us conclude that [Formula: see text] is a negative instance, and simplifications, which might let us simplify [Formula: see text] by removing or contracting some edges. Most of these tests and simplifications are performed “locally”, by looking at the crossings involving a single edge or face of a connected component [Formula: see text] of [Formula: see text]; however, some tests and simplifications have to consider certain global structures in [Formula: see text], which we call [Formula: see text]-donuts. If no test concludes that [Formula: see text] is a negative instance of the pssttm problem, then the simplifications eventually transform [Formula: see text] into an equivalent [Formula: see text]-planar topological multigraph on which we can apply the cited linear-time algorithm by Di Battista and Frati.
6
Abbasi, Mozhgan, Jochem Verrelst, Mohsen Mirzaei, Safar Marofi und Hamid Reza Riyahi Bakhtiari. „Optimal Spectral Wavelengths for Discriminating Orchard Species Using Multivariate Statistical Techniques“. Remote Sensing 12, Nr. 1 (23.12.2019): 63. http://dx.doi.org/10.3390/rs12010063.
Der volle Inhalt der QuelleAnnotation:
Sustainable management of orchard fields requires detailed information about the tree types, which is a main component of precision agriculture programs. To this end, hyperspectral imagery can play a major role in orchard tree species mapping. Efficient use of hyperspectral data in combination with field measurements requires the development of optimized band selection strategies to separate tree species. In this study, field spectroscopy (350 to 2500 nm) was performed through scanning 165 spectral leaf samples of dominant orchard tree species (almond, walnut, and grape) in Chaharmahal va Bakhtiyari province, Iran. Two multivariable methods were employed to identify the optimum wavelengths: the first includes three-step approach ANOVA, random forest classifier (RFC) and principal component analysis (PCA), and the second employs partial least squares (PLS). For both methods we determined whether tree species can be spectrally separated using discriminant analysis (DA) and then the optimal wavelengths were identified for this purpose. Results indicate that all species express distinct spectral behaviors at the beginning of the visible range (from 350 to 439 nm), the red edge and the near infrared wavelengths (from 701 to 1405 nm). The ANOVA test was able to reduce primary wavelengths (2151) to 792, which had a significant difference (99% confidence level), then the RFC further reduced the wavelengths to 118. By removing the overlapping wavelengths, the PCA represented five components (99.87% of variance) which extracted optimal wavelengths were: 363, 423, 721, 1064, and 1388 nm. The optimal wavelengths for the species discrimination using the best PLS-DA model (100% accuracy) were at 397, 515, 647, 1386, and 1919 nm.
7
Raghavan, S., und Rui Zhang. „Influence Maximization with Latency Requirements on Social Networks“. INFORMS Journal on Computing 34, Nr. 2 (März 2022): 710–28. http://dx.doi.org/10.1287/ijoc.2021.1095.
Der volle Inhalt der QuelleAnnotation:
Targeted marketing strategies are of significant interest in the smartapp economy. Typically, one seeks to identify individuals to strategically target in a social network so that the network is influenced at a minimal cost. In many practical settings, the effects of direct influence predominate, leading to the positive influence dominating set with partial payments (PIDS-PP) problem that we discuss in this paper. The PIDS-PP problem is NP-complete because it generalizes the dominating set problem. We discuss several mixed integer programming formulations for the PIDS-PP problem. First, we describe two compact formulations on the payment space. We then develop a stronger compact extended formulation. We show that when the underlying graph is a tree, this compact extended formulation provides integral solutions for the node selection variables. In conjunction, we describe a polynomial-time dynamic programming algorithm for the PIDS-PP problem on trees. We project the compact extended formulation onto the payment space, providing an equivalently strong formulation that has exponentially many constraints. We present a polynomial time algorithm to solve the associated separation problem. Our computational experience on a test bed of 100 real-world graph instances (with up to approximately 465,000 nodes and 835,000 edges) demonstrates the efficacy of our strongest payment space formulation. It finds solutions that are on average 0.4% from optimality and solves 80 of the 100 instances to optimality. Summary of Contribution: The study of influence propagation is important in a number of applications including marketing, epidemiology, and healthcare. Typically, in these problems, one seeks to identify individuals to strategically target in a social network so that the entire network is influenced at a minimal cost. With the ease of tracking consumers in the smartapp economy, the scope and nature of these problems have become larger. Consequently, there is considerable interest across multiple research communities in computationally solving large-scale influence maximization problems, which thus represent significant opportunities for the development of operations research–based methods and analysis in this interface. This paper introduces the positive influence dominating set with partial payments (PIDS-PP) problem, an influence maximization problem where the effects of direct influence predominate, and it is possible to make partial payments to nodes that are not targeted. The paper focuses on model development to solve large-scale PIDS-PP problems. To this end, starting from an initial base optimization model, it uses several operations research model strengthening techniques to develop two equivalent models that have strong computational performance (and can be theoretically shown to be the best model for trees). Computational experiments on a test bed of 100 real-world graph instances (with up to approximately 465,000 nodes and 835,000 edges) attest to the efficacy of the best model, which finds solutions that are on average 0.4% from optimality and solves 80 of the 100 instances to optimality.
8
Zhang, Zhijun, Muhammad Awais Umar, Xiaojun Ren, Basharat Rehman Ali, Mujtaba Hussain und Xiangmei Li. „Tree-Antimagicness of Web Graphs and Their Disjoint Union“. Mathematical Problems in Engineering 2020 (09.04.2020): 1–6. http://dx.doi.org/10.1155/2020/4565829.
Der volle Inhalt der QuelleAnnotation:
In graph theory, the graph labeling is the assignment of labels (represented by integers) to edges and/or vertices of a graph. For a graph G=V,E, with vertex set V and edge set E, a function from V to a set of labels is called a vertex labeling of a graph, and the graph with such a function defined is called a vertex-labeled graph. Similarly, an edge labeling is a function of E to a set of labels, and in this case, the graph is called an edge-labeled graph. In this research article, we focused on studying super ad,d-T4,2-antimagic labeling of web graphs W2,n and isomorphic copies of their disjoint union.
9
Haghir Chehreghani, Morteza. „Unsupervised representation learning with Minimax distance measures“. Machine Learning 109, Nr. 11 (28.07.2020): 2063–97. http://dx.doi.org/10.1007/s10994-020-05886-4.
Der volle Inhalt der QuelleAnnotation:
Abstract We investigate the use of Minimax distances to extract in a nonparametric way the features that capture the unknown underlying patterns and structures in the data. We develop a general-purpose and computationally efficient framework to employ Minimax distances with many machine learning methods that perform on numerical data. We study both computing the pairwise Minimax distances for all pairs of objects and as well as computing the Minimax distances of all the objects to/from a fixed (test) object. We first efficiently compute the pairwise Minimax distances between the objects, using the equivalence of Minimax distances over a graph and over a minimum spanning tree constructed on that. Then, we perform an embedding of the pairwise Minimax distances into a new vector space, such that their squared Euclidean distances in the new space equal to the pairwise Minimax distances in the original space. We also study the case of having multiple pairwise Minimax matrices, instead of a single one. Thereby, we propose an embedding via first summing up the centered matrices and then performing an eigenvalue decomposition to obtain the relevant features. In the following, we study computing Minimax distances from a fixed (test) object which can be used for instance in K-nearest neighbor search. Similar to the case of all-pair pairwise Minimax distances, we develop an efficient and general-purpose algorithm that is applicable with any arbitrary base distance measure. Moreover, we investigate in detail the edges selected by the Minimax distances and thereby explore the ability of Minimax distances in detecting outlier objects. Finally, for each setting, we perform several experiments to demonstrate the effectiveness of our framework.
10
Toyonaga, Kenji. „The location of classified edges due to the change in the geometric multiplicity of an eigenvalue in a tree“. Special Matrices 7, Nr. 1 (01.01.2019): 257–62. http://dx.doi.org/10.1515/spma-2019-0019.
Der volle Inhalt der QuelleAnnotation:
Abstract Given a combinatorially symmetric matrix A whose graph is a tree T and its eigenvalues, edges in T can be classified in four categories, based upon the change in geometric multiplicity of a particular eigenvalue, when the edge is removed. We investigate a necessary and sufficient condition for each classification of edges. We have similar results as the case for real symmetric matrices whose graph is a tree. We show that a g-2-Parter edge, a g-Parter edge and a g-downer edge are located separately from each other in a tree, and there is a g-neutral edge between them. Furthermore, we show that the distance between a g-downer edge and a g-2-Parter edge or a g-Parter edge is at least 2 in a tree. Lastly we give a combinatorially symmetric matrix whose graph contains all types of edges.
Dissertationen zum Thema "EDGE TEST TREE GRAPH"
1
Jones, Brian Douglas. „Tree components in random graph processes with non-uniform edge probabilities /“. The Ohio State University, 1995. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487867541733461.
Der volle Inhalt der Quelle
2
Bouchat, Rachelle R. „ALGEBRAIC PROPERTIES OF EDGE IDEALS“. UKnowledge, 2008. http://uknowledge.uky.edu/gradschool_diss/618.
Der volle Inhalt der QuelleAnnotation:
Given a simple graph G, the corresponding edge ideal IG is the ideal generated by the edges of G. In 2007, Ha and Van Tuyl demonstrated an inductive procedure to construct the minimal free resolution of certain classes of edge ideals. We will provide a simplified proof of this inductive method for the class of trees. Furthermore, we will provide a comprehensive description of the finely graded Betti numbers occurring in the minimal free resolution of the edge ideal of a tree. For specific subclasses of trees, we will generate more precise information including explicit formulas for the projective dimensions of the quotient rings of the edge ideals. In the second half of this thesis, we will consider the class of simple bipartite graphs known as Ferrers graphs. In particular, we will study a class of monomial ideals that arise as initial ideals of the defining ideals of the toric rings associated to Ferrers graphs. The toric rings were studied by Corso and Nagel in 2007, and by studying the initial ideals of the defining ideals of the toric rings we are able to show that in certain cases the toric rings of Ferrers graphs are level.
3
Gouveia, da silva Thiago. „The Minimum Labeling Spanning Tree and Related Problems“. Thesis, Avignon, 2018. http://www.theses.fr/2018AVIG0278.
Der volle Inhalt der QuelleAnnotation:
Soit L un ensemble fini d’éléments appelés étiquettes. On appelle graphe étiqueté simple, un graphe simple dans lequel à chaque arête est associée une étiquette prise dans L. Le problème de l’arbre couvrant de nombre d’étiquettes minimal (en anglais: the minimum labeling spanning tree problem, MLSTP) est un problème d’optimisation combinatoire consistant à trouver un arbre couvrant dans un graphe étiqueté simple en utilisant un nombre minimum d’étiquettes. Le problème est NP-dur. Il a fait l’objet d’un nombre important de recherche au cours des dernières années. L’une de ces directions de recherche a par ailleurs conduit à l’étude d’une généralisation du problème dite problème généralisée de l’arbre couvrant de nombre d’étiquettes minimal(en anglais: the generalized minimum labeling spanning tree problem, GMLSTP). Le problème GMLSTP modélise les situations dans lesquelles plusieurs étiquettes peuvent être assignées à un arête. Les deux problèmes ont plusieurs applications pratiques dans des domaines importants tels que la conception de réseaux informatiques, la conception de réseaux de transport multimodaux et la compression de données. Nous proposons dans cette thèse plusieurs résultats théoriques contribuant à l’implantation de nouveaux schémas de résolution pratique de ces problèmes. En particulier, sur le plan théorique, nous avons introduit de nouveaux concepts, définitions, propriétés et théorèmes utiles, ainsi qu’une étude polyédrale du domaine des points réalisables d’une nouvelle formulation de GMLSTP. Cette formulation et son analyse ont permi le développement d’algorithmes de branchement et de coupe (branch-and-cut) pour la résolution exacte des problèmes. De nouvelles heuristiques ont été également développées — telles que l’algorithme basé sur la métaheuristique MSLB, et l’heuristique constructive pMVCA. Des résultats d’expériences numériques sur des benchmarks du problème MLSTP sont données. Elles démontrent la qualité des approches proposées dans cette thèse puisque, aussi bien pour les approches exactes qu’approchées, nous obtenons, comparativement à l’état de l’art du domaine, les meilleurs résultats de la littératureThe minimum labeling spanning tree problem (MLSTP) is a combinatorial optimization problem that consists in finding a spanning tree in a simple edge-labeled graph, i.e., a graph inwhich each edge has one label associated, by using a minimum number of labels. It is anNP-hard problem that has attracted substantial research attention in recent years. In its turn,the generalized minimum labeling spanning tree problem (GMLSTP) is a generalization of theMLSTP that allows the situation in which multiple labels can be assigned to an edge. Bothproblems have several practical applications in important areas such as computer network design, multimodal transportation network design, and data compression. This thesis addressesseveral connectivity problems defined over edge-labeled graphs, in special the minimum labeling spanning tree problem and its generalized version. The contributions in this work can beclassified between theoretical and practical. On the theoretical side, we have introduced newuseful concepts, definitions, properties and theorems regarding edge-labeled graphs, as well asa polyhedral study on the GMLSTP. On the practical side, we have proposed new heuristics— such as the metaheuristic-based algorithm MSLB, and the constructive heuristic pMVCA —and exact methods — such as new mathematical formulations and branch-and-cut algorithms —for solving the GMLSTP. Computational experiments over well established benchmarks for theMLSTP are reported, showing that the new approaches introduced in this work have achievedthe best results for both heuristic and exact methods in comparison with the state-of-the-artmethods in the literature
O Problema da Árvore Geradora com Rotulação Mínima (MLSTP, do inglês minimum labelingspanning tree problem) é um problema de otimização combinatória que consiste em encontraruma árvore de cobertura em um grafo com arestas rotuladas, isto é, um grafo no qual cada arestapossui um rótulo associado, utilizando o menor número de rótulos. Este problema é NP-difícile tem atraído bastante atenção em pesquisas nos últimos anos. Por sua vez, o Problema Generalizado da Árvore Geradora com Rotulação Mínima (GMLSTP, do inglês generalized minimum labeling spanning tree problem) é uma generalização do MLSTP na qual se permite que múltiplos rótulos sejam associados a uma aresta. Ambos os problemas tem aplicações práticas em áreas importantes, como Projeto de Redes de Computadores, Projeto de Redes de Transporte Multimodais e Compactação de Dados. Esta tese aborda vários problemas de conectividade definidos em grafos com arestas rotuladas, em especial o Problema da Árvore Geradora com Rotulação Mínima e sua versão generalizada. As contribuições neste trabalho podem ser classificadas entre teóricas e práticas. Dentre as contribuições teóricas, introduzimos novos conceitos,definições, propriedades e teoremas úteis em relação a grafos com arestas rotuladas, bem como um estudo poliédrico sobre o GMLSTP. Dentre as contribuições práticas, propusemos novas heurísticas _ como o algoritmo baseado na metaheurística MSLB e a heurística construtiva pMVCA _ e métodos exatos _ como novas formulações matemáticas e algoritmos branch- and-cut _ para resolver o GMLSTP. Os experimentos computacionais realizados utilizando conjuntos de instâncias bem estabelecidos para o MLSTP são relatados, mostrando que as novas abordagens introduzidas neste trabalho alcançaram os melhores resultados para métodosheurísticos e exatos em comparação com estado da arte da literatura
4
Bencke, Cinara Salete Curra. „Estudo da fenologia de espécies arbóreas em uma floresta semidecídua no Parque Estadual de Itapuã, Viamão, RS“. reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2005. http://hdl.handle.net/10183/10000.
Der volle Inhalt der QuelleAnnotation:
O presente estudo foi realizado em uma floresta semidecídua no Parque Estadual de Itapuã, no município de Viamão, RS. Este trabalho teve como objetivos: a) descrever e comparar o comportamento fenológico de espécies arbóreas em duas formações fisionômica distintas – uma área de interior de floresta e outra de borda; b) realizar análises de correlação entre as fenofases e as variáveis climáticas pluviosidade e temperatura para o período de estudo e para os seis meses anteriores, e também verificar a existência de correlação entre as fenofases e os dados médios de pluviosidade e temperatura para um período de 30 anos; e c) verificar a existência (ou não) de sazonalidade nas áreas amostradas. O clima da região é subtropical úmido sem estação seca, com temperatura média anual em torno de 19,5oC. A precipitação anual varia entre 1.100 e 1.300 mm e as chuvas são bem distribuídas ao longo do ano. Dados de floração, frutificação, queda foliar e brotamento foram coletados mensalmente para um total de 54 espécies no período entre outubro/2002 e março/2004. As relações entre as fenofases vegetativas e as variáveis climáticas foram similares em ambas as áreas, sugerindo que as espécies amostradas são afetadas de modo semelhante pelo clima. A queda foliar e o brotamento ocorreram simultaneamente nas duas áreas. A queda foliar manteve um padrão irregular e decrescente durante as observações em ambas as áreas, sem picos pronunciados de atividade. Já o brotamento foi intermitente durante o período de observações. O comportamento fenológico das fenofases reprodutivas diferiu nas áreas amostradas. O pico principal de floração ocorreu um mês antes na borda, e no interior da floresta esta fenofase exibiu um pico secundário que não foi observado na borda.Esta foi a fenofase que apresentou mais correlações significativas com as variáveis climáticas consideradas. Assim como a floração, a frutificação também foi constante, evidenciando assincronia entre as espécies. A frutificação apresentou correlação altamente significativa com a pluviosidade do sexto mês precedente no interior da floresta, e correlação significativa com a temperatura 4–5 meses antes e com a temperatura média para o período de 30 anos na borda. As análises de correlação mostraram que as fenofases apresentaram mais correlações significativas com a temperatura do que com a pluviosidade, e que a área de borda teve mais correlações significativas do que a área de interior de floresta. O teste de Rayleigh mostrou que, das fenofases observadas, apenas a queda foliar foi sazonal, embora as demais fenofases tenham apresentado picos de atividade pronunciados no período de amostragem.This study was conducted in a semideciduous forest at Itapuã State Park, Viamão municipality, Rio Grande do Sul State, southern Brazil. Its objectives were to: a) describe and compare the phenological patterns of arboreal plant species at two physiognomically distinct sites, one in the interior and the other at the edge of the forest; b) estimate the correlation between the phenological phases and the climatic variables precipitation and temperature for the study period and for each one of the six preceding months, and also between the phenophases and the average monthly rainfall and temperature for a 30 years period; and c) test for the existence of seasonality among the phenological phases in the study sites. Climate in the region is subtropical humid with no pronounced dry season. The mean annual temperature is around 19.5oC. The annual precipitation varies from 1.100 to 1.300 mm and the rains are well distributed throughout the year. Data on flowering, fruiting, leaf fall and leaf flushing for 54 species were collected monthly from October 2002 to March 2004. The relationship between the vegetative phenological phases and climatic variables was similar in both areas, suggesting that the sampled species are affected by the local climate in a similar way. Leaf fall and flushing were simultaneous in both areas. Leaf fall showed an irregular and decreasing pattern throughout the sampling period, with no pronounced peaks of activity. Leaf flushing was intermittent during the observation period. The phenological pattern of the reproductive phenophases differed in the study sites. The main flowering peak occurred one month earlier at the edge site, and at the forest interior this phenological phase showed a secondary peak not detected at the edge. Flowering was the phenological phase most strongly correlated with the climatic variables. Flowering and fruiting were constant, evidencing asynchrony among the sampled species. Fruiting was highly correlated with precipitation 6 months before at the forest interior site, and significantly correlated with temperature 4–5 months before and with average temperature for the 30 year period at the edge site. Correlation analysis showed that the phenological phases were more strongly associated with temperature than with rainfall, and that the edge had more significant correlations with climatic variables than the forest interior. The Rayleigh test revealed that, of all phenological phases considered, only leaf fall was truly seasonal, even though the other phenophases showed pronounced peaks of activity throughout the sampling period.
5
Meinhardt, Llopis Enric. „Morphological and statistical techniques for the analysis of 3D images“. Doctoral thesis, Universitat Pompeu Fabra, 2011. http://hdl.handle.net/10803/22719.
Der volle Inhalt der QuelleAnnotation:
Aquesta tesi proposa una estructura de dades per
emmagatzemar imatges tridimensionals. L'estructura da dades té
forma d'arbre i codifica les components connexes dels conjunts de
nivell de la imatge. Aquesta estructura és la eina bàsica per
moltes aplicacions proposades: operadors morfològics
tridimensionals, visualització d'imatges mèdiques, anàlisi
d'histogrames de color, seguiment d'objectes en vídeo i detecció
de vores. Motivada pel problema de la completació de vores, la
tesi conté un estudi de com l'eliminació de soroll mitjançant variació
total anisòtropa es pot fer servir per calcular conjunts de
Cheeger en mètriques anisòtropes. Aquests conjunts de Cheeger
anisòtrops es poden utilitzar per trobar òptims globals d'alguns
funcionals per completar vores. També estan relacionats amb
certs invariants afins que s'utilitzen en reconeixement
d'objectes, i en la tesi s'explicita aquesta relació.This thesis proposes a tree data structure to encode the connected components of level sets of 3D images. This data structure is applied as a main tool in several proposed applications: 3D morphological operators, medical image visualization, analysis of color histograms, object tracking in videos and edge detection. Motivated by the problem of edge linking, the thesis contains also an study of anisotropic total variation denoising as a tool for computing anisotropic Cheeger sets. These anisotropic Cheeger sets can be used to find global optima of a class of edge linking functionals. They are also related to some affine invariant descriptors which are used in object recognition, and this relationship is laid out explicitly.
6
Tahraoui, Mohammed Amin. „Coloring, packing and embedding of graphs“. Phd thesis, Université Claude Bernard - Lyon I, 2012. http://tel.archives-ouvertes.fr/tel-00995041.
Der volle Inhalt der QuelleAnnotation:
In this thesis, we investigate some problems in graph theory, namelythe graph coloring problem, the graph packing problem and tree pattern matchingfor XML query processing. The common point between these problems is that theyuse labeled graphs.In the first part, we study a new coloring parameter of graphs called the gapvertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G whichinduces a vertex distinguishing labeling of G such that the label of each vertex isgiven by the difference between the highest and the lowest colors of its adjacentedges. The minimum number of colors required for a gap vertex-distinguishing edgecoloring of G is called the gap chromatic number of G and is denoted by gap(G).We will compute this parameter for a large set of graphs G of order n and we evenprove that gap(G) 2 fn E 1; n; n + 1g.In the second part, we focus on graph packing problems, which is an area ofgraph theory that has grown significantly over the past several years. However, themajority of existing works focuses on unlabeled graphs. In this thesis, we introducefor the first time the packing problem for a vertex labeled graph. Roughly speaking,it consists of graph packing which preserves the labels of the vertices. We studythe corresponding optimization parameter on several classes of graphs, as well asfinding general bounds and characterizations.The last part deal with the query processing of a core subset of XML query languages:XML twig queries. An XML twig query, represented as a small query tree,is essentially a complex selection on the structure of an XML document. Matching atwig query means finding all the occurrences of the query tree embedded in the XMLdata tree. Many holistic twig join algorithms have been proposed to match XMLtwig pattern. Most of these algorithms find twig pattern matching in two steps. Inthe first one, a query tree is decomposed into smaller pieces, and solutions againstthese pieces are found. In the second step, all of these partial solutions are joinedtogether to generate the final solutions. In this part, we propose a novel holistictwig join algorithm, called TwigStack++, which features two main improvementsin the decomposition and matching phase. The proposed solutions are shown to beefficient and scalable, and should be helpful for the future research on efficient queryprocessing in a large XML database.
7
GOEL, RUCHI. „A PARADIGM FOR TESTING WEB APPLICATION“. Thesis, 2011. http://dspace.dtu.ac.in:8080/jspui/handle/repository/13894.
Der volle Inhalt der QuelleAnnotation:
M.TECHFor any work of literature, a fundamental issue is to identify the individual(s) who wrote it, and conversely, to identify all of the works that belong to a given individual or to identify the individual who writes many papers on same topic. A web application is an application that can be accessed via a web browser over a network. Web applications contain client side code and server side code. Web applications undergo changes in the maintenance phase, and retesting changed programs is done thereafter. To retest a program after changes, we can select a subset of the whole test suite on the condition that the selected subset will give confidence about covering the changes. As an important method to ensure quality of web applications, Regression Testing techniques are required for adequate selection of these subsets of test cases. This project compares regression testing techniques for web applications based on a safe approach that covers changed elements and other potentially affected ones. In this project we have implemented a new technique to select test cases for regression testing on web applications based on the Edge Test Tree Graph (ETT) as presented in the paper “A Practical Web Testing Model for Web Application Testing” by Zhongsheng Qian, Huakiou Miao, Hongwei Zeng., School of Computer Engineering and Science, Shanghai University, China[5]. This work proposes a Web Testing Model for web application testing. It starts from constructing the ETT (Event Test Tree) of web application. An algorithm is designed to derive an ETT (Event Test Tree) from the EDG from ETT, we extract the path expressions to generate test paths. Then a test specification is made in C++ to generate the required test cases. Then the web application is modified and Regression Testing is applied. The regression test selection technique is based on identifying changed and potentially changed components. Empirical results show that this technique selects a reduced number of test cases that experience only affected and potentially affected components.we have also studied paper by Abbas Tarhini, Zahi Ismail, Nashat Mansour, Regression Testing Web Applications, 2008 International Conference on Advanced Computer Theory and Engineering[3].
8
Klimošová, Tereza. „Immersions and edge-disjoint linkages“. Master's thesis, 2011. http://www.nusl.cz/ntk/nusl-313889.
Der volle Inhalt der QuelleAnnotation:
Graph immersions are a natural counterpart to the widely studied concepts of graph minors and topological graph minors, and yet their theory is much less developed. In the present work we search for sufficient conditions for the existence of the immersions and the properties of the graphs avoiding an immersion of a fixed graph. We prove that large tree-with of 4-edge-connected graph implies the existence of immersion of any 4-regular graph on small number of vertices and that large maximum degree of 3-edge-connected graph implies existence of immersion of any 3-regular graph on small number of vertices.
Buchteile zum Thema "EDGE TEST TREE GRAPH"
1
Boyacı, Arman, Tınaz Ekim, Mordechai Shalom und Shmuel Zaks. „Graphs of Edge-Intersecting Non-splitting Paths in a Tree: Towards Hole Representations“. In Graph-Theoretic Concepts in Computer Science, 115–26. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-45043-3_11.
Der volle Inhalt der Quelle
2
Ajith E und Uma N. „SCRIBO: A Graph Visualizer & Analytical Tool“. In Advances in Transdisciplinary Engineering. IOS Press, 2023. http://dx.doi.org/10.3233/atde221254.
Der volle Inhalt der QuelleAnnotation:
Data science is a very visual field of computer science where everything needs to be depicted graphically in order to derive new forms of data and conclusions from it. This paper introduces visualization techniques where graphs can be better rendered using advance techniques such as vertex and edge clipping against the view port, rendering a large drawing area by panning the view port to focus on a specific region, labelling vertex data with numeric , text and images and advanced analytic algorithms such as analyzing and finding the shortest path between two vertices using Dijkstra’s, Floyd, finding the minimum spanning tree using Prims and Kruskal’s and traversing all vertices in a graph using Breadth first search and Depth first search. Practically any issue if it can be condensed into a graph data structure format can be sent to this program and are graphically evaluated to discover new information. This paper explains the above-mentioned techniques in detail and how they can work together to create an advanced visualization tool for data scientists working with bidirectional weighted relational data that is graphs.
3
Nardelli, Enrico, Guido Proietti und Peter Widmayer. „Finding All the Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures“. In Graph Algorithms and Applications 2, 455–73. WORLD SCIENTIFIC, 2004. http://dx.doi.org/10.1142/9789812794741_0020.
Der volle Inhalt der Quelle
4
Hosseininia, Mahtab, und Faraz Dadgostari. „Connectivity“. In Graph Theory for Operations Research and Management, 37–47. IGI Global, 2013. http://dx.doi.org/10.4018/978-1-4666-2661-4.ch004.
Der volle Inhalt der QuelleAnnotation:
In this chapter, the concept of graph connectivity is introduced. In the first section, some concepts such as walk, path, component and connected graph are defined, and connectedness of a graph from the viewpoint of vertex connectivity, and also, edge connectivity are discussed. Then, blocks and block tree of graphs are illustrated. In addition, connectivity in directed graphs is introduced. Furthermore, in the last section, two graph traversal algorithms, depth first search and breadth first search, are described to investigate the connectedness of directed and undirected graphs.
5
Margalit, Dan. „Groups Acting on Trees“. In Office Hours with a Geometric Group Theorist. Princeton University Press, 2017. http://dx.doi.org/10.23943/princeton/9780691158662.003.0003.
Der volle Inhalt der QuelleAnnotation:
This chapter considers groups acting on trees. It examines which groups act on which spaces and, if a group does act on a space, what it says about the group. These spaces are called trees—that is, connected graphs without cycles. A group action on a tree is free if no nontrivial element of the group preserves any vertex or any edge of the tree. The chapter first presents the theorem stating that: If a group G acts freely on a tree, then G is a free group. The condition that G is free is equivalent to the condition that G acts freely on a tree. The discussion then turns to the Farey tree and shows how to construct the Farey complex using the Farey graph. The chapter concludes by describing free and non-free actions on trees. Exercises and research projects are included.
6
Maitra, Indra Kanta, und Samir Kumar Bandhyopadhyaay. „Adaptive Edge Detection Method towards Features Extraction from Diverse Medical Imaging Technologies“. In Advances in Data Mining and Database Management, 159–92. IGI Global, 2017. http://dx.doi.org/10.4018/978-1-5225-1776-4.ch007.
Der volle Inhalt der QuelleAnnotation:
The CAD is a relatively young interdisciplinary technology, has had a tremendous impact on medical diagnosis specifically cancer detection. The accuracy of CAD to detect abnormalities on medical image analysis requires a robust segmentation algorithm. To achieve accurate segmentation, an efficient edge-detection algorithm is essential. Medical images like USG, X-Ray, CT and MRI exhibit diverse image characteristics but are essentially collection of intensity variations from which specific abnormalities are needed to be isolated. In this chapter a robust medical image enhancement and edge detection algorithm is proposed, using tree-based adaptive thresholding technique. It has been compared with different classical edge-detection techniques using one sample two tail t-test to exam whether the null hypothesis can be supported. The proposed edge-detection algorithm showing 0.07 p-values and 2.411 t-stat where a = 0.025. Moreover the proposed edge is single pixeled and connected which is very significant for medical edge detection.
7
Maitra, Indra Kanta, und Samir Kumar Bandhyopadhyaay. „Adaptive Edge Detection Method Towards Features Extraction From Diverse Medical Imaging Technologies“. In Computer Vision, 1245–78. IGI Global, 2018. http://dx.doi.org/10.4018/978-1-5225-5204-8.ch052.
Der volle Inhalt der QuelleAnnotation:
The CAD is a relatively young interdisciplinary technology, has had a tremendous impact on medical diagnosis specifically cancer detection. The accuracy of CAD to detect abnormalities on medical image analysis requires a robust segmentation algorithm. To achieve accurate segmentation, an efficient edge-detection algorithm is essential. Medical images like USG, X-Ray, CT and MRI exhibit diverse image characteristics but are essentially collection of intensity variations from which specific abnormalities are needed to be isolated. In this chapter a robust medical image enhancement and edge detection algorithm is proposed, using tree-based adaptive thresholding technique. It has been compared with different classical edge-detection techniques using one sample two tail t-test to exam whether the null hypothesis can be supported. The proposed edge-detection algorithm showing 0.07 p-values and 2.411 t-stat where α = 0.025. Moreover the proposed edge is single pixeled and connected which is very significant for medical edge detection.
8
Xu, Jinxin, Xueling Yang, Jinbo Zuo, Jiayan Mu und Zhiqiang Guan. „Forward-Backward Diffusion and Pruning-Based Cost Aggregation for Non-Local Stereo Matching“. In Advances in Transdisciplinary Engineering. IOS Press, 2022. http://dx.doi.org/10.3233/atde221021.
Der volle Inhalt der QuelleAnnotation:
Minimum spanning tree (MST) has been devised for non-local cost aggregation to solve the stereo matching problem. However, the cost aggregation is employed directly from leaf toward root node, then in an inverse pass without considering any decision rules. And a small amount of noise is also existed in stereo image pairs. Both of the limitations often lead to failure in achieving more competitive results. This paper presents a novel stereo matching algorithm using forward-backward diffusion and pruning-based cost aggregation. In “forward-backward” process, the raw image pairs are smoothened on a horizontal tree structure as well as retaining image edges sharp. During cost aggregation, the MST where a complete graph involves the whole image pixels is cut off self-adaptively when the depth edge information is referred to. Each node in this tree receives supports from all other nodes which belong to similar depth regions. Meanwhile, an enhanced edge similarity function between two nearest neighboring nodes is formulated to deal with the small-weight-accumulation problem in textureless regions. Consequently, the cost volume can be well aggregated. The proposed method is demonstrated on Middlebury v.2 & v.3 datasets and can obtain good performance in disparity accuracy compared with other five MST based stereo matching methods.
9
Yuan, Peng, Zuogang Zheng, Xinshuo Yuan, Lanhua Zhang, Mei Wang, Xiaoyan Wang und Xucai Ji. „Classification of Characteristic Factors of Brain Functional Network Using Decision Tree“. In Frontiers in Artificial Intelligence and Applications. IOS Press, 2022. http://dx.doi.org/10.3233/faia220581.
Der volle Inhalt der QuelleAnnotation:
In order to explore the classification methods from imaging data, we propose to establish the feature classification order by building a classification tree with characteristic factors of brain functional network aided by calculating of network topology based on graph theory. By preprocessing the imaging data and modeling the networks with professional platform, we get the topology parameters as the input of the C4.5 decision tree, and then get the classification feature and classification tree by calculating the information gain ratio. The results show that the classification prefers holistic characteristics and quality characteristics. By programming and the samples test, it is feasible to extend the classification with network characters learning based on the processing results of multi-modal imaging data and machine learning algorithms.
10
Moharam, Riham, Ehab Morsy und Ismail A. Ismail. „T-Spanner Problem“. In Handbook of Research on Machine Learning Innovations and Trends, 1–21. IGI Global, 2017. http://dx.doi.org/10.4018/978-1-5225-2229-4.ch001.
Der volle Inhalt der QuelleAnnotation:
The t-spanner problem is a popular combinatorial optimization problem and has different applications in communication networks and distributed systems. This chapter considers the problem of constructing a t-spanner subgraph H in a given undirected edge-weighted graph G in the sense that the distance between every pair of vertices in H is at most t times the shortest distance between the two vertices in G. The value of t, called the stretch factor, quantifies the quality of the distance approximation of the corresponding t-spanner subgraph. This chapter studies two variations of the problem, the Minimum t-Spanner Subgraph (MtSS) and the Minimum Maximum Stretch Spanning Tree(MMST). Given a value for the stretch factor t, the MtSS problem asks to find the t-spanner subgraph of the minimum total weight in G. The MMST problem looks for a tree T in G that minimizes the maximum distance between all pairs of vertices in V (i.e., minimizing the stretch factor of the constructed tree). It is easy to conclude from the literatures that the above problems are NP-hard. This chapter presents genetic algorithms that returns a high quality solution for those two problems.
Konferenzberichte zum Thema "EDGE TEST TREE GRAPH"
1
Wu, Qinzhuo, Qi Zhang und Zhongyu Wei. „An Edge-Enhanced Hierarchical Graph-to-Tree Network for Math Word Problem Solving“. In Findings of the Association for Computational Linguistics: EMNLP 2021. Stroudsburg, PA, USA: Association for Computational Linguistics, 2021. http://dx.doi.org/10.18653/v1/2021.findings-emnlp.127.
Der volle Inhalt der Quelle
2
Huang, Tianhao, Guohao Dai, Yu Wang und Huazhong Yang. „HyVE: Hybrid vertex-edge memory hierarchy for energy-efficient graph processing“. In 2018 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 2018. http://dx.doi.org/10.23919/date.2018.8342150.
Der volle Inhalt der Quelle
3
Feng, Yuhong, Meihong Guo, Kezhong Lu, Zhong Ming, Haoming Zhong, Wentong Cai und Zengxiang Li. „Optimize the FP-Tree Based Graph Edge Weight Computation on Multi-core MapReduce Clusters“. In 2017 IEEE 23rd International Conference on Parallel and Distributed Systems (ICPADS). IEEE, 2017. http://dx.doi.org/10.1109/icpads.2017.00060.
Der volle Inhalt der Quelle
4
Lu, Zhicheng, Ruochen Li, Huamiao Hu und Wen-an Zhou. „A code clone detection algorithm based on graph convolution network with AST tree edge“. In 2021 IEEE 21st International Conference on Software Quality, Reliability and Security Companion (QRS-C). IEEE, 2021. http://dx.doi.org/10.1109/qrs-c55045.2021.00156.
Der volle Inhalt der Quelle
5
Muresan, Valentin, X. Wang, Valentina Muresan und M. Vladutiu. „The left edge algorithm and the tree growing technique in block-test scheduling under power constraints“. In Proceedings 18th IEEE VLSI Test Symposium. IEEE, 2000. http://dx.doi.org/10.1109/vtest.2000.843873.
Der volle Inhalt der Quelle
6
Junetty, Rakel, Diari Indriati und Bowo Winarno. „Edge irregular reflexive labeling of palm tree graph C3−B2,r and C3−B3,r“. In INTERNATIONAL CONFERENCE OF MATHEMATICS AND MATHEMATICS EDUCATION (I-CMME) 2021. AIP Publishing, 2022. http://dx.doi.org/10.1063/5.0116566.
Der volle Inhalt der Quelle
7
Belli, Fevzi, Axel Hollmann und Markus Kleinselbeck. „A Graph-Model-Based Testing Method Compared with the Classification Tree Method for Test Case Generation“. In 2009 Third IEEE International Conference on Secure Software Integration and Reliability Improvement (SSIRI). IEEE, 2009. http://dx.doi.org/10.1109/ssiri.2009.40.
Der volle Inhalt der Quelle
8
Da Silva, Thiago Gouveia. „The Minimum Labeling Spanning Tree and Related Problems“. In XXXII Concurso de Teses e Dissertações da SBC. Sociedade Brasileira de Computação - SBC, 2019. http://dx.doi.org/10.5753/ctd.2019.6333.
Der volle Inhalt der QuelleAnnotation:
The minimum labeling spanning tree problem (MLSTP) is a combinatorial optimization problem that consists in finding a spanning tree in a simple edge-labeled graph, i.e., a graph in which each edge has one label associated, by using a minimum number of labels. It is an NP-hard problem that has attracted substantial research attention in recent years. In its turn, the generalized minimum labeling spanning tree problem (GMLSTP) is a generalization of the MLSTP that allows the situation in which multiple labels can be assigned to an edge. Both problems have several practical applications in important areas such as computer network design, multimodal transportation network design, and data compression. The thesis addresses several connectivity problems defined over edge-labeled graphs, in special the minimum labeling spanning tree problem and its generalized version. The contributions in the work can be classified between theoretical and practical. On the theoretical side, it has introduced new useful concepts, definitions, properties and theorems regarding edge-labeled graphs, as well as a polyhedral study on the GMLSTP. On the practical side, we have proposed new heuristics and new mathematical formulations and branch-and-cut algorithms. The new approaches introduced have achieved the best results for both heuristic and exact methods in comparison with the state-of-the-art.
9
Hebrard, Emmanuel, und George Katsirelos. „Clause Learning and New Bounds for Graph Coloring“. In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/856.
Der volle Inhalt der QuelleAnnotation:
Graph coloring is a major component of numerous allocation and scheduling problems. We introduce a hybrid CP/SAT approach to graph coloring based on exploring Zykov’s tree: for two non-neighbors, either they take a different color and there might as well be an edge between them, or they take the same color and we might as well merge them. Branching on whether two neighbors get the same color yields a symmetry-free tree with complete graphs as leaves, which correspond to colorings of the original graph. We introduce a new lower bound for this problem based on Mycielskian graphs; a method to produce a clausal explanation of this bound for use in a CDCL algorithm; and a branching heuristic emulating Brelaz on the Zykov tree. The combination of these techniques in a branch- and-bound search outperforms Dsatur and other SAT-based approaches on standard benchmarks both for finding upper bounds and for proving lower bounds.
10
Cohen, Jaime, Luiz A. Rodrigues und Elias P. Duarte Jr. „Improved Parallel Implementations of Gusfield’s Cut Tree Algorithm“. In Simpósio em Sistemas Computacionais de Alto Desempenho. Sociedade Brasileira de Computação, 2011. http://dx.doi.org/10.5753/wscad.2011.17275.
Der volle Inhalt der QuelleAnnotation:
This work presents parallel versions of Gusfield’s cut tree algorithm and the proposal of two heuristics aimed at improving their performance. Cut trees are a compact representation of the edge-connectivity between every pair of vertices of an undirected graph. Cut trees have a vast number of applications in combinatorial optimization and in the analysis of networks originated in many applied fields. However, surprisingly few works have been published on the practical performance of cut tree algorithms. This paper describes two parallel versions of Gusfield’s cut tree algorithm and presents extensive experimental results which show a significant speedup on most real and synthetic graphs in our dataset.