Bibliografie tematiche / Trees (graph theory)

Indice

Articoli di riviste
Tesi
Libri
Capitoli di libri
Atti di convegni

Letteratura scientifica selezionata sul tema "Trees (graph theory)"

Autore: Grafiati

Pubblicato: 4 giugno 2021

Ultima modifica: 25 luglio 2024

Cita una fonte nei formati APA, MLA, Chicago, Harvard e in molti altri stili

Scegli il tipo di fonte:

Consulta la lista di attuali articoli, libri, tesi, atti di convegni e altre fonti scientifiche attinenti al tema "Trees (graph theory)".

Accanto a ogni fonte nell'elenco di riferimenti c'è un pulsante "Aggiungi alla bibliografia". Premilo e genereremo automaticamente la citazione bibliografica dell'opera scelta nello stile citazionale di cui hai bisogno: APA, MLA, Harvard, Chicago, Vancouver ecc.

Puoi anche scaricare il testo completo della pubblicazione scientifica nel formato .pdf e leggere online l'abstract (il sommario) dell'opera se è presente nei metadati.

Articoli di riviste sul tema "Trees (graph theory)"

McKee, Terry A. "Subgraph trees in graph theory". Discrete Mathematics 270, n. 1-3 (agosto 2003): 3–12. http://dx.doi.org/10.1016/s0012-365x(03)00161-4.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Thenge, J. D., B. Surendranath Reddy e Rupali S. Jain. "Contribution to Soft Graph and Soft Tree". New Mathematics and Natural Computation 15, n. 01 (25 dicembre 2018): 129–43. http://dx.doi.org/10.1142/s179300571950008x.

Testo completo

Abstract (sommario):

Soft set theory introduced by D. Molodstov is a new theory which deals with uncertainty. Connected graphs can be represented by using soft sets called soft graphs. In the present paper, we introduce the tabular representation of soft graph and define radius, diameter, center and degree of soft graph. We also define union, product of soft graphs and soft trees. We then derive some properties of radius, degree of vertex in soft graph and soft trees.

Gli stili APA, Harvard, Vancouver, ISO e altri

Козневски e E. Kozniewski. "Roof Skeletons and Graph Theory Trees". Geometry & Graphics 4, n. 1 (17 marzo 2016): 12–20. http://dx.doi.org/10.12737/18054.

Testo completo

Abstract (sommario):

The problem of constructing roofs of many papers [1; 6; 7; 9; etc.]. In this case, some studies suggested to use a computer and special programs [10; 13; 16; etc.]. The geometry of the efficient design of roofs is actual scientific direction, so in the educational process of architectural and building trades made corresponding innovations [2; 8; 14; 15; 17–20; etc.]. The roofs considered in this article are defined as special geometric polyhedral surfaces, on the basis of two assumptions: (1) all eaves of a roof form a planar (simply-connected or k-connected) polygon called the base, (2) every hipped roof end makes the same slope angle with the (horizontal) plane which contains the base. All the vertices and edges of such a roof, forming the roof skeleton, determine a graph. The orthogonal projection of a roof skeleton onto the base plane leads to a planar graph. On the basis of [11] and [12] and continuing the investigations for regular roofs, we formulate further properties which enable studying the shapes of the roofs spread over simply connected v-gons for an arbitrary integer v (v ≥ 3). We also introduce new operations: splitting and grafting of graphs, and formulate some properties of these operations. By means of such operations, the creation of a graph with cycles using two or more trees is possible. In particular, the operation of the grafting of a roof allows modeling an atrial roof.

Gli stili APA, Harvard, Vancouver, ISO e altri

Janson, Svante. "Random trees in a graph and trees in a random graph". Mathematical Proceedings of the Cambridge Philosophical Society 100, n. 2 (settembre 1986): 319–30. http://dx.doi.org/10.1017/s0305004100066111.

Testo completo

Abstract (sommario):

This paper treats two related sets of problems in the theory of random graphs. In Sections 2 and 3 we study random spanning subtrees of a complete graph (or, equivalently, random labelled trees). It is shown that the number of common edges of two such random trees asymptotically has a Poisson distribution with expectation 2. Similar results are obtained for the number of edges in the intersection or union of more than two random trees.

Gli stili APA, Harvard, Vancouver, ISO e altri

Markhabatov, Nurlan. "Approximations of Acyclic Graphs". Bulletin of Irkutsk State University. Series Mathematics 40 (2022): 104–11. http://dx.doi.org/10.26516/1997-7670.2022.40.104.

Testo completo

Abstract (sommario):

In this paper, approximations of acyclic graphs are studied. It is proved that any theory of an acyclic graph (tree) of finite diameter is pseudofinite with respect to acyclic graphs (trees), that is, any such theory is approximated by theories of finite structures (acyclic graphs, trees). It is also proved that an acyclic graph of infinite diameter with infinite number of rays is pseudofinite.

Gli stili APA, Harvard, Vancouver, ISO e altri

Zeen El Deen, Mohamed R. "Enumeration of spanning trees in prisms of some graphs". Proyecciones (Antofagasta) 42, n. 2 (1 dicembre 2023): 339–91. http://dx.doi.org/10.22199/issn.0717-6279-4664.

Testo completo

Abstract (sommario):

In graph theory, a prism over a graph G is the cartesian product of the graph G with P₂. The purpose of this work is to investigate the complexity of the prisms of some path and cycle-related graphs. In particular, we obtain simpler and more explicit formulas for the complexity of a special class of prisms of path-related graphs: fan graph, ladder graph, the composition Pn[P₂] graph, and book graph. Moreover, we obtain straightforward formulas for the complexity of a special class of prisms of cycle-related graphs: wheel graph, gear graph, prism graph, n−crossed prism graph, mirror graph M(Cn) of even cycle Cn, twisted prism, total graph T(Cn) of the cycle Cn, the friendship graph, the flower graph, and planner sunflower graph. These closed formulas are deduced using some basic properties of block matrix, recurrence relation, eigenvalues of circulant matrices, and orthogonal polynomials.

Gli stili APA, Harvard, Vancouver, ISO e altri

JOHANNSEN, DANIEL, MICHAEL KRIVELEVICH e WOJCIECH SAMOTIJ. "Expanders Are Universal for the Class of All Spanning Trees". Combinatorics, Probability and Computing 22, n. 2 (3 gennaio 2013): 253–81. http://dx.doi.org/10.1017/s0963548312000533.

Testo completo

Abstract (sommario):

A graph is calleduniversalfor a given graph class(or, equivalently,-universal) if it contains a copy of every graph inas a subgraph. The construction of sparse universal graphs for various classeshas received a considerable amount of attention. There is particular interest in tight-universal graphs, that is, graphs whose number of vertices is equal to the largest number of vertices in a graph from. Arguably, the most studied case is that whenis some class of trees. In this work, we are interested in(n,Δ), the class of alln-vertex trees with maximum degree at most Δ. We show that everyn-vertex graph satisfying certain natural expansion properties is(n,Δ)-universal. Our methods also apply to the case when Δ is some function ofn. Since random graphs are known to be good expanders, our result implies, in particular, that there exists a positive constantcsuch that the random graphG(n,cn−1/3log2n) is asymptotically almost surely (a.a.s.) universal for(n,O(1)). Moreover, a corresponding result holds for the random regular graph of degreecn2/3log2n. Another interesting consequence is the existence of locally sparsen-vertex(n,Δ)-universal graphs. For example, we show that one can (randomly) constructn-vertex(n,O(1))-universal graphs with clique number at most five. This complements the construction of Bhatt, Chung, Leighton and Rosenberg (1989), whose(n,Δ)-universal graphs with merelyO(n)edges contain large cliques of size Ω(Δ). Finally, we show that random graphs are robustly(n,Δ)-universal in the context of the Maker–Breaker tree-universality game.

Gli stili APA, Harvard, Vancouver, ISO e altri

Raczek, Joanna, e Rita Zuazua. "Progress on Roman and Weakly Connected Roman Graphs". Mathematics 9, n. 16 (5 agosto 2021): 1846. http://dx.doi.org/10.3390/math9161846.

Testo completo

Abstract (sommario):

A graph G for which γR(G)=2γ(G) is the Roman graph, and if γRwc(G)=2γwc(G), then G is the weakly connected Roman graph. In this paper, we show that the decision problem of whether a bipartite graph is Roman is a co-NP-hard problem. Next, we prove similar results for weakly connected Roman graphs. We also study Roman trees improving the result of M.A. Henning’s A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002). Moreover, we give a characterization of weakly connected Roman trees.

Gli stili APA, Harvard, Vancouver, ISO e altri

Finbow, Stephen, e Christopher M. van Bommel. "γ-Graphs of Trees". Algorithms 12, n. 8 (30 luglio 2019): 153. http://dx.doi.org/10.3390/a12080153.

Testo completo

Abstract (sommario):

For a graph G = ( V , E ) , the γ -graph of G, denoted G ( γ ) = ( V ( γ ) , E ( γ ) ) , is the graph whose vertex set is the collection of minimum dominating sets, or γ -sets of G, and two γ -sets are adjacent in G ( γ ) if they differ by a single vertex and the two different vertices are adjacent in G. In this paper, we consider γ -graphs of trees. We develop an algorithm for determining the γ -graph of a tree, characterize which trees are γ -graphs of trees, and further comment on the structure of γ -graphs of trees and its connections with Cartesian product graphs, the set of graphs which can be obtained from the Cartesian product of graphs of order at least two.

Gli stili APA, Harvard, Vancouver, ISO e altri

NATH, MILAN, e SOMNATH PAUL. "GRAPH TRANSFORMATION AND DISTANCE SPECTRAL RADIUS". Discrete Mathematics, Algorithms and Applications 05, n. 03 (settembre 2013): 1350014. http://dx.doi.org/10.1142/s1793830913500146.

Testo completo

Abstract (sommario):

Trees are very common in the theory and applications of combinatorics. In this paper, we consider graphs whose underlying structure is a tree and study the behavior of the distance spectral radius under a graph transformation. As an application, we find the corona tree that maximizes the distance spectral radius among all corona trees with a fixed maximum degree. We also find the graph with minimal (maximal) distance spectral radius among all corona trees. Finally, we determine the graph with minimal distance spectral radius in a special class of corona trees.

Gli stili APA, Harvard, Vancouver, ISO e altri

Più fonti

Tesi sul tema "Trees (graph theory)"

Dawson, Shelly Jean. "Minimal congestion trees". CSUSB ScholarWorks, 2006. https://scholarworks.lib.csusb.edu/etd-project/3005.

Testo completo

Abstract (sommario):

Analyzes the results of M.I. Ostrovskii's theorem of inequalities which estimate the minimal edge congestion for finite simple graphs. Uses the generic results of the theorem to examine and further reduce the parameters of inequalities for specific families of graphs, particularly complete graphs and complete bipartite graphs. Also, explores a possible minimal congestion tree for some grids while forming a conjecture for all grids.

Gli stili APA, Harvard, Vancouver, ISO e altri

Tang, Yin Ping Wendy. "Bandwidth of some classes of full directed trees". HKBU Institutional Repository, 1998. http://repository.hkbu.edu.hk/etd_ra/256.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Montgomery, Richard Harford. "Minors and spanning trees in graphs". Thesis, University of Cambridge, 2015. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.709278.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Mahoney, James Raymond. "Tree Graphs and Orthogonal Spanning Tree Decompositions". PDXScholar, 2016. http://pdxscholar.library.pdx.edu/open_access_etds/2944.

Testo completo

Abstract (sommario):

Given a graph G, we construct T(G), called the tree graph of G. The vertices of T(G) are the spanning trees of G, with edges between vertices when their respective spanning trees differ only by a single edge. In this paper we detail many new results concerning tree graphs, involving topics such as clique decomposition, planarity, and automorphism groups. We also investigate and present a number of new results on orthogonal tree decompositions of complete graphs.

Gli stili APA, Harvard, Vancouver, ISO e altri

Humphries, Peter John. "Combinatorial Aspects of Leaf-Labelled Trees". Thesis, University of Canterbury. Mathematics and Statistics, 2008. http://hdl.handle.net/10092/1801.

Testo completo

Abstract (sommario):

Leaf-labelled trees are used commonly in computational biology and in other disciplines, to depict the ancestral relationships and present-day similarities between both extant and extinct species. Studying these trees from a mathematical perspective provides a foundation for developing tools and techniques that have practical applications. We begin by examining some quartet problems, namely determining the number of quartets that are required to infer the structure of a particular supertree. The quartet graph is introduced as a tool for tackling quartet problems, and is subsequently used to give new characterisations of compatible, definitive and identifying quartet sets. We then turn to investigating some properties of the subtrees induced by a collection of trees. This is motivated in part by the problem of reconstructing two or more trees simultaneously from their combined collection of subtrees. We also use some ideas drawn from Ramsey theory to show the existence of arbitrarily large common subtrees. Finally, we explore some extremal properties of the metric that is induced by the tree bisection and reconnection operation. This includes finding new (asymptotically) tight upper and lower bounds on both the size of the neighbourhoods in the metric space and on the diameter of the corresponding adjacency graph.

Gli stili APA, Harvard, Vancouver, ISO e altri

Zhang, Xinyi. "Expected lengths of minimum spanning trees". Access to citation, abstract and download form provided by ProQuest Information and Learning Company; downloadable PDF file, 139 p, 2008. http://proquest.umi.com/pqdweb?did=1597617641&sid=6&Fmt=2&clientId=8331&RQT=309&VName=PQD.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Tam, Wing Ka. "The strong chromatic index of cubic Halin graphs". HKBU Institutional Repository, 2003. http://repository.hkbu.edu.hk/etd_ra/516.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Jayasooriya, Arachchilage Dinush Lanka Panditharathna. "Spanning Trees of Certain Types". OpenSIUC, 2016. https://opensiuc.lib.siu.edu/theses/2049.

Testo completo

Abstract (sommario):

A Spanning tree of a graph G is a subgraph that is a tree which concludes all of the vertices of G. And a graph G is bipartite if the vertex set of G can be partitioned in to two sets A and B, such that every edge of G joins a vertex of A and a vertex of B. We can see that every tree(including spanning tree) is bipartite. We define type of a spanning tree using this idea as follows: We divide vertices of a spanning trees in to two partitions A and B by using its bipartition. Then, we define type of the spanning tree by (| A |, | B |), provided | A | less than or equal to | B |. We first identify the characteristics for a graph to have a spanning trees of a certain type. Then, implement some theorems about the type.

Gli stili APA, Harvard, Vancouver, ISO e altri

Curran, Sean P. "Independent trees in 4-connected graphs". Diss., Georgia Institute of Technology, 2003. http://hdl.handle.net/1853/29842.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Janzen, David. "The smallest irreducible lattices in the product of trees /". Thesis, McGill University, 2007. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=101884.

Testo completo

Abstract (sommario):

We produce a nonpositively curved square complex, X, containing exactly four squares. Its universal cover, X̃ ≅ T4 x T 4, is isomorphic to the product of two 4-valent trees. The group, pi1X, is a lattice in Aut (X̃) but π1X is not virtually a nontrivial product of free groups. There is no such example with fewer than four squares. The main ingredient in our analysis is that X̃ contains an "anti-torus" which is a certain aperiodically tiled plane.

Gli stili APA, Harvard, Vancouver, ISO e altri

Più fonti

Libri sul tema "Trees (graph theory)"

1960-, Chauvin Brigitte, Cohen Serge 1964-, Rouault Alain 1949- e Workshop on Trees (1995 : Versailles, France), a cura di. Trees: Workshop in Versailles, June 14-16, 1995. Basel: Birkhäuser, 1996.

Cerca il testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Limnios, N. Fault trees. London, UK: ISTE, 2007.

Cerca il testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Introduction to [lambda]-trees. Singapore: World Scientific, 2001.

Cerca il testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

A, Evstigneev V., a cura di. Graph theory for programmers: Algorithms for processing trees. Dordrecht: Kluwer Academic, 2000.

Cerca il testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Crouch, Peter. Trees, bialgebras and intrinsic numerical algorithms. Chicago, IL: Dept. of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, 1990.

Cerca il testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Dingzhu, Du, Smith J. M e Rubinstein J. H, a cura di. Advances in Steiner trees. Dordrecht: Kluwer Academic, 2000.

Cerca il testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Rubin, Matatyahu. The reconstruction of trees from their automorphism groups. Providence, R.I: American Mathematical Society, 1993.

Cerca il testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Treewidth: Computations and approximations. Berlin: Springer-Verlag, 1994.

Cerca il testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Kasʹi͡anov, V. N. Graph theory for programmers: Algorithms for processing trees. Dordrecht: Kluwer Academic, 2000.

Cerca il testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Leister, Karen J. Using minimal spanning trees to compare the reliability of network topologies. Hampton, Va: Langley Research Center, 1990.

Cerca il testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Più fonti

Capitoli di libri sul tema "Trees (graph theory)"

Saoub, Karin R. "Trees". In Graph Theory, 123–68. Boca Raton: CRC Press, 2021. | Series: Textbooks in mathematics: Chapman and Hall/CRC, 2021. http://dx.doi.org/10.1201/9781138361416-3.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Sumner, David. "Forbidden Trees". In Graph Theory, 69–89. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-97686-0_8.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Rahman, Md Saidur. "Trees". In Basic Graph Theory, 47–62. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-49475-3_4.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Yadav, Santosh Kumar. "Trees". In Advanced Graph Theory, 51–88. Cham: Springer International Publishing, 2023. http://dx.doi.org/10.1007/978-3-031-22562-8_2.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Diestel, Reinhard. "Minors Trees and WQO". In Graph Theory, 333–75. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/978-3-642-14279-6_12.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Henning, Michael A., e Jan H. van Vuuren. "Trees". In Graph and Network Theory, 115–44. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-03857-0_5.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Kasyanov, Victor N., e Viadimir A. Evstigneev. "Spanning Trees". In Graph Theory for Programmers, 121–73. Dordrecht: Springer Netherlands, 2000. http://dx.doi.org/10.1007/978-94-011-4122-2_3.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Kasyanov, Victor N., e Viadimir A. Evstigneev. "Structural Trees". In Graph Theory for Programmers, 175–222. Dordrecht: Springer Netherlands, 2000. http://dx.doi.org/10.1007/978-94-011-4122-2_4.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Kasyanov, Victor N., e Viadimir A. Evstigneev. "Syntax Trees". In Graph Theory for Programmers, 293–336. Dordrecht: Springer Netherlands, 2000. http://dx.doi.org/10.1007/978-94-011-4122-2_6.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Kasyanov, Victor N., e Viadimir A. Evstigneev. "Information Trees". In Graph Theory for Programmers, 337–73. Dordrecht: Springer Netherlands, 2000. http://dx.doi.org/10.1007/978-94-011-4122-2_7.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Atti di convegni sul tema "Trees (graph theory)"

Dreher, D., e J. L. Walker. "Connections between computation trees and graph covers". In 2009 Information Theory and Applications Workshop (ITA). IEEE, 2009. http://dx.doi.org/10.1109/ita.2009.5044971.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Onete, Cristian E., e A. Maria Cristina C. Onete. "Finding spanning trees and Hamiltonian circuits in an un-oriented graph an algebraic approach". In 2011 European Conference on Circuit Theory and Design (ECCTD). IEEE, 2011. http://dx.doi.org/10.1109/ecctd.2011.6043384.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Zhou, Hong, e Kwun-Lon Ting. "Spanning Tree Based Topological Optimization of Compliant Mechanisms". In ASME 2005 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. ASMEDC, 2005. http://dx.doi.org/10.1115/detc2005-84608.

Testo completo

Abstract (sommario):

In graph theory, spanning trees connect all the vertices together using minimum number of edges. A topological optimization method of compliant mechanisms is presented based on spanning tree theory. A valid topology is regarded as a network connecting input, output, support and intermediate nodes, which contains at least one spanning tree among the introduced nodes. Invalid disconnected topologies can be weeded out if no spanning tree is included. No further deformation analysis and performance evaluation is needed for invalid disconnected topologies. Problem-dependent objectives are optimized for topological optimization of compliant mechanisms. Constraints about maximum input displacement and input force, maximum stress and overlapping connections are directly imposed during the optimization process. The discrete optimization problem is solved by genetic algorithm with penalty function handling constraints. An example is presented to verify the effectiveness of the proposed optimization procedure.

Gli stili APA, Harvard, Vancouver, ISO e altri

Yan, Hong-Sen, Feng-Ming Ou e Ming-Feng Tang. "An Algorithm for the Enumeration of Serial and/or Parallel Combinations of Kinematic Building Blocks". In ASME 2004 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. ASMEDC, 2004. http://dx.doi.org/10.1115/detc2004-57295.

Testo completo

Abstract (sommario):

An algorithm is presented, based on graph theory, for enumerating all feasible serial and/or parallel combined mechanisms from the given rotary or translational power source and specific kinematic building blocks. Through the labeled out-tree representations for the configurations of combined mechanisms, the enumeration procedure is developed by adapting the algorithm for the enumeration of trees. A rotary power source and four kinematic building blocks: a crank-rocker linkage, a rack-pinion, a double-slider mechanism, and a cam-follower mechanism, are chosen as the combination to illustrate the algorithm. And, two examples are provided to validate the algorithm.

Gli stili APA, Harvard, Vancouver, ISO e altri

Wu, Junran, Shangzhe Li, Jianhao Li, Yicheng Pan e Ke Xu. "A Simple yet Effective Method for Graph Classification". In Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}. California: International Joint Conferences on Artificial Intelligence Organization, 2022. http://dx.doi.org/10.24963/ijcai.2022/497.

Testo completo

Abstract (sommario):

In deep neural networks, better results can often be obtained by increasing the complexity of previously developed basic models. However, it is unclear whether there is a way to boost performance by decreasing the complexity of such models. Intuitively, given a problem, a simpler data structure comes with a simpler algorithm. Here, we investigate the feasibility of improving graph classification performance while simplifying the learning process. Inspired by structural entropy on graphs, we transform the data sample from graphs to coding trees, which is a simpler but essential structure for graph data. Furthermore, we propose a novel message passing scheme, termed hierarchical reporting, in which features are transferred from leaf nodes to root nodes by following the hierarchical structure of coding trees. We then present a tree kernel and a convolutional network to implement our scheme for graph classification. With the designed message passing scheme, the tree kernel and convolutional network have a lower runtime complexity of O(n) than Weisfeiler-Lehman subtree kernel and other graph neural networks of at least O(hm). We empirically validate our methods with several graph classification benchmarks and demonstrate that they achieve better performance and lower computational consumption than competing approaches.

Gli stili APA, Harvard, Vancouver, ISO e altri

Cohen, Jaime, Luiz A. Rodrigues e 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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

Almeida, Raquel, Ewa Kijak, Simon Malinowski e Silvio Jamil F. Guimarães. "Learning on graphs and hierarchies". In Anais Estendidos da Conference on Graphics, Patterns and Images. Sociedade Brasileira de Computação - SBC, 2023. http://dx.doi.org/10.5753/sibgrapi.est.2023.27449.

Testo completo

Abstract (sommario):

Hierarchies, as described in mathematical morphology, represent nested regions of interest that facilitate high-level analysis and provide mechanisms for coherent data organization. Represented as hierarchical trees, they have formalisms intersecting with graph theory and applications that can be conveniently generalized. However, due to the deterministic algorithms, the multiform representations, and the absence of a direct way to evaluate the hierarchical structure, it is hard to insert hierarchical information into a learning framework and benefit from the recent advances in the field. This work aims to create a learning framework that can operate with hierarchical data and is agnostic to the input and the application. The idea is to study ways to transform the data to a regular representation required by most learning models while preserving the rich information in the hierarchical structure. The methods in this study use edgeweighted image graphs and hierarchical trees as input, evaluating different proposals on the edge detection and segmentation tasks. The model of choice is the Random Forest, a fast, inspectable, scalable method. The experiments in this work are an outline of the original study in the related Ph.D. thesis. They demonstrate that it is possible to create a learning framework dependent only on the hierarchical data that performs well in multiple tasks.

Gli stili APA, Harvard, Vancouver, ISO e altri

León, Jared. "A generalization of the block decomposition for k-connected graphs". In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2022. http://dx.doi.org/10.5753/etc.2022.223106.

Testo completo

Abstract (sommario):

The decomposition of a connected graph by the set of its cut-vertices, sometimes called the "block decomposition" or "block tree" of a graph, is a well known and basic concept in graph theory. This decomposition, however, does not provide any meaningful information when applied to a $k$-connected graph for $k \geq 2$. There has been a number of attempts to generalize the construction of the block decomposition of a graph for the case of $k$-connected graphs. In this work, we present an outline of one such attempt by Karpov. We also present some applications of this decomposition to the study of planarity, the chromatic number, and critically $2$-connected graphs.

Gli stili APA, Harvard, Vancouver, ISO e altri

Huang, Xuanxiang, Yacine Izza, Alexey Ignatiev e Joao Marques-Silva. "On Efficiently Explaining Graph-Based Classifiers". In 18th International Conference on Principles of Knowledge Representation and Reasoning {KR-2021}. California: International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/kr.2021/34.

Testo completo

Abstract (sommario):

Recent work has shown that not only decision trees (DTs) may not be interpretable but also proposed a polynomial-time algorithm for computing one PI-explanation of a DT. This paper shows that for a wide range of classifiers, globally referred to as decision graphs, and which include decision trees and binary decision diagrams, but also their multi-valued variants, there exist polynomial-time algorithms for computing one PI-explanation. In addition, the paper also proposes a polynomial-time algorithm for computing one contrastive explanation. These novel algorithms build on explanation graphs (XpG's). XpG's denote a graph representation that enables both theoretical and practically efficient computation of explanations for decision graphs. Furthermore, the paper proposes a practically efficient solution for the enumeration of explanations, and studies the complexity of deciding whether a given feature is included in some explanation. For the concrete case of decision trees, the paper shows that the set of all contrastive explanations can be enumerated in polynomial time. Finally, the experimental results validate the practical applicability of the algorithms proposed in the paper on a wide range of publicly available benchmarks.

Gli stili APA, Harvard, Vancouver, ISO e altri

Hebrard, Emmanuel, e 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.

Testo completo

Abstract (sommario):

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.

Gli stili APA, Harvard, Vancouver, ISO e altri

Offriamo sconti su tutti i piani premium per gli autori le cui opere sono incluse in raccolte letterarie tematiche. Contattaci per ottenere un codice promozionale unico!