Готові списки джерел за темами / Trees (graph theory)

Добірка наукової літератури з теми "Trees (graph theory)"

Автор: Grafiati
Опубліковано: 4 червня 2021
Оновлено: 25 липня 2024

Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями

Оберіть тип джерела:

Зміст

Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Trees (graph theory)".

Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.

Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.

Статті в журналах з теми "Trees (graph theory)"

1

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

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
2

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

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
3

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

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
4

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

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
5

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.

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
6

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

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
7

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

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
8

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

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
9

Finbow, Stephen, та Christopher M. van Bommel. "γ-Graphs of Trees". Algorithms 12, № 8 (30 липня 2019): 153. http://dx.doi.org/10.3390/a12080153.

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
10

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

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
Більше джерел

Дисертації з теми "Trees (graph theory)"

1

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

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
2

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

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
3

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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
4

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

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
5

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

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
6

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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
7

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

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
8

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

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
9

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

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
10

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.

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
Більше джерел

Книги з теми "Trees (graph theory)"

1

1960-, Chauvin Brigitte, Cohen Serge 1964-, Rouault Alain 1949-, and Workshop on Trees (1995 : Versailles, France), eds. Trees: Workshop in Versailles, June 14-16, 1995. Basel: Birkhäuser, 1996.

Знайти повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
2

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

Знайти повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
3

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

Знайти повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
4

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

Знайти повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
5

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

Знайти повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
6

Dingzhu, Du, Smith J. M, and Rubinstein J. H, eds. Advances in Steiner trees. Dordrecht: Kluwer Academic, 2000.

Знайти повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
7

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

Знайти повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
8

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

Знайти повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
9

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

Знайти повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
10

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

Знайти повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
Більше джерел

Частини книг з теми "Trees (graph theory)"

1

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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
2

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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
3

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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
4

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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
5

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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
6

Henning, Michael A., and 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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
7

Kasyanov, Victor N., and 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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
8

Kasyanov, Victor N., and 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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
9

Kasyanov, Victor N., and 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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
10

Kasyanov, Victor N., and 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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.

Тези доповідей конференцій з теми "Trees (graph theory)"

1

Dreher, D., and 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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
2

Onete, Cristian E., and 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.

Повний текст джерела
Стилі APA, Harvard, Vancouver, ISO та ін.
3

Zhou, Hong, and 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.

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
4

Yan, Hong-Sen, Feng-Ming Ou, and 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.

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
5

Wu, Junran, Shangzhe Li, Jianhao Li, Yicheng Pan, and 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.

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
6

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

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
7

Almeida, Raquel, Ewa Kijak, Simon Malinowski, and 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.

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
8

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.

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
9

Huang, Xuanxiang, Yacine Izza, Alexey Ignatiev, and 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.

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
10

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

Повний текст джерела
Анотація:
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.
Стилі APA, Harvard, Vancouver, ISO та ін.
Також вас можуть зацікавити розширені добірки на тему "Trees (graph theory)" для конкретних типів джерел:
Статті в журналах Дисертації Книги
Ми пропонуємо знижки на всі преміум-плани для авторів, чиї праці увійшли до тематичних добірок літератури. Зв'яжіться з нами, щоб отримати унікальний промокод!

До бібліографії