Relevant bibliographies by topics / Trees (graph theory)

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers

Academic literature on the topic 'Trees (graph theory)'

Author: Grafiati
Published: 4 June 2021
Last updated: 25 July 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Trees (graph theory).'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
9

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

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
More sources

Dissertations / Theses on the topic "Trees (graph theory)"

1

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

Full text
Abstract:
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, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

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

Full text
Abstract:
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, and other styles
5

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

Full text
Abstract:
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, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

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

Full text
Abstract:
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, and other styles
9

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
Abstract:
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, and other styles
More sources

Books on the topic "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.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

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

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

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

Find full text
APA, Harvard, Vancouver, ISO, and other styles
4

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

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

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

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

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

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

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

Find full text
APA, Harvard, Vancouver, ISO, and other styles
8

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

Find full text
APA, Harvard, Vancouver, ISO, and other styles
9

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

Find full text
APA, Harvard, Vancouver, ISO, and other styles
10

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

Find full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
You might also be interested in the extended bibliographies on the topic 'Trees (graph theory)' for particular source types:
Journal articles Dissertations / Theses Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography