Heavy path decomposition

Last updated

In combinatorial mathematics and theoretical computer science, heavy path decomposition (also called heavy-light decomposition) is a technique for decomposing a rooted tree into a set of paths. In a heavy path decomposition, each non-leaf node selects one "heavy edge", the edge to the child that has the greatest number of descendants (breaking ties arbitrarily). The selected edges form the paths of the decomposition.

Contents

Decomposition into paths

If the edges of a tree T are partitioned into a set of heavy edges and light edges, with one heavy edge from each non-leaf node to one of its children, then the subgraph formed by the heavy edges consists of a set of paths, with each non-leaf vertex belonging to exactly one path, the one containing its heavy edge. Leaf nodes of the tree that are not the endpoint of a heavy edge may be considered as forming paths of length zero. In this way, each vertex belongs to exactly one of the paths. Each path has a head vertex, its topmost vertex.

Alternatively, the paths of heavy edges may be extended by including one light edge, the one from the head of the path to its parent. [1] In this variation of the decomposition, some vertices belong to multiple paths, but every edge of T belongs to exactly one path.

The path tree

The paths of the decomposition may themselves be organized into a tree called the "path tree", "heavy path tree", or "compressed tree". Each node of the path tree corresponds to a path of the heavy path decomposition. If p is a path of the heavy path decomposition, then the parent of p in the path tree is the path containing the parent of the head of p. The root of the path tree is the path containing the root of the original tree. Alternatively, the path tree may be formed from the original tree by edge contraction of all the heavy edges.

A "light" edge of a given tree is an edge that was not selected as part of the heavy path decomposition. If a light edge connects two tree nodes x and y, with x the parent of y, then x must have at least twice as many descendants as y. Therefore, on any root-to-leaf path of a tree with n nodes, there can be at most log2 n light edges. Equivalently, the path tree has height at most log2 n.

Applications

Heavy path decomposition was introduced by Sleator & Tarjan (1983) as part of the amortized analysis of their link/cut tree structure, [2] and by Harel & Tarjan (1984) as part of their data structure for lowest common ancestors, [3] The link/cut tree data structure uses a partition of a dynamic tree into paths that is not necessarily the heavy path decomposition; its analysis uses a potential function measuring its distance from the heavy path decomposition, and the small height of the path tree implies that each data structure operation performs only a small number of steps that cannot be charged against improvements to this function. [2] In the lowest common ancestor data structure, the decomposition is used to embed the input tree into a complete binary tree of logarithmic depth, allowing each query to be solved by constant-time bitwise operations. [3]

Subsequent applications of heavy path decomposition have included solving the level ancestor problem, [4] computing the edit distance between trees, [5] [6] graph drawing and greedy embedding, [7] [8] [9] finding a path near all nodes of a given graph, [10] fault diagnosis in fiber-optic communication networks, [1] and decoding grammar-based codes, [11] among others.

Related Research Articles

<span class="mw-page-title-main">Minimum spanning tree</span> Least-weight tree connecting graph vertices

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

<span class="mw-page-title-main">Dijkstra's algorithm</span> Graph search algorithm

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

<span class="mw-page-title-main">Strongly connected component</span> Partition of a graph whose components are reachable from all vertices

In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected. It is possible to test the strong connectivity of a graph, or to find its strongly connected components, in linear time (that is, Θ(V + E)).

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.

<span class="mw-page-title-main">Bridge (graph theory)</span> Edge in node-link graph whose removal would disconnect the graph

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth.

In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition. Pathwidth is also known as interval thickness, vertex separation number, or node searching number.

In graph theory and computer science, the lowest common ancestor (LCA) of two nodes v and w in a tree or directed acyclic graph (DAG) T is the lowest node that has both v and w as descendants, where we define each node to be a descendant of itself.

A link/cut tree is a data structure for representing a forest, a set of rooted trees, and offers the following operations:

<span class="mw-page-title-main">SPQR tree</span> Representation of a graphs triconnected components

In graph theory, a branch of mathematics, the triconnected components of a biconnected graph are a system of smaller graphs that describe all of the 2-vertex cuts in the graph. An SPQR tree is a tree data structure used in computer science, and more specifically graph algorithms, to represent the triconnected components of a graph. The SPQR tree of a graph may be constructed in linear time and has several applications in dynamic graph algorithms and graph drawing.

<span class="mw-page-title-main">Strong product of graphs</span> Binary operation in graph theory

In graph theory, the strong product is a way of combining two graphs to make a larger graph. Two vertices are adjacent in the strong product when they come from pairs of vertices in the factor graphs that are either adjacent or identical. The strong product is one of several different graph product operations that have been studied in graph theory. The strong product of any two graphs can be constructed as the union of two other products of the same two graphs, the Cartesian product of graphs and the tensor product of graphs.

<span class="mw-page-title-main">Pseudoforest</span> Graph with one cycle per component

In graph theory, a pseudoforest is an undirected graph in which every connected component has at most one cycle. That is, it is a system of vertices and edges connecting pairs of vertices, such that no two cycles of consecutive edges share any vertex with each other, nor can any two cycles be connected to each other by a path of consecutive edges. A pseudotree is a connected pseudoforest.

<span class="mw-page-title-main">Cartesian tree</span>

In computer science, a Cartesian tree is a binary tree derived from a sequence of numbers. The smallest number in the sequence is at the root of the tree; its left and right subtrees are constructed recursively from the subsequences to the left and right of this number. When all numbers are distinct, the Cartesian tree is uniquely defined from the properties that it is heap-ordered and that a symmetric (in-order) traversal of the tree returns the original sequence.

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of vertices from an n-vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.

<span class="mw-page-title-main">Unrooted binary tree</span>

In mathematics and computer science, an unrooted binary tree is an unrooted tree in which each vertex has either one or three neighbors.

In graph theory, the modular decomposition is a decomposition of a graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a proper subset of another. Modules therefore lead to a recursive (hierarchical) decomposition of the graph, instead of just a partition.

In graph theory, Robbins' theorem, named after Herbert Robbins (1939), states that the graphs that have strong orientations are exactly the 2-edge-connected graphs. That is, it is possible to choose a direction for each edge of an undirected graph G, turning it into a directed graph that has a path from every vertex to every other vertex, if and only if G is connected and has no bridge.

In distributed computing and geometric graph theory, greedy embedding is a process of assigning coordinates to the nodes of a telecommunications network in order to allow greedy geographic routing to be used to route messages within the network. Although greedy embedding has been proposed for use in wireless sensor networks, in which the nodes already have positions in physical space, these existing positions may differ from the positions given to them by greedy embedding, which may in some cases be points in a virtual space of a higher dimension, or in a non-Euclidean geometry. In this sense, greedy embedding may be viewed as a form of graph drawing, in which an abstract graph is embedded into a geometric space.

In graph theory, a bipolar orientation or st-orientation of an undirected graph is an assignment of a direction to each edge that causes the graph to become a directed acyclic graph with a single source s and a single sink t, and an st-numbering of the graph is a topological ordering of the resulting directed acyclic graph.

<span class="mw-page-title-main">Split (graph theory)</span>

In graph theory, a split of an undirected graph is a cut whose cut-set forms a complete bipartite graph. A graph is prime if it has no splits. The splits of a graph can be collected into a tree-like structure called the split decomposition or join decomposition, which can be constructed in linear time. This decomposition has been used for fast recognition of circle graphs and distance-hereditary graphs, as well as for other problems in graph algorithms.

References

  1. 1 2 Harvey, Nicholas J. A.; Pătraşcu, Mihai; Wen, Yonggang; Yekhanin, Sergey; Chan, Vincent W. S. (2007), "Non-adaptive fault diagnosis for all-optical networks via combinatorial group testing on graphs", 26th IEEE International Conference on Computer Communications (INFOCOM 2007), pp. 697–705, doi:10.1109/INFCOM.2007.87
  2. 1 2 Sleator, Daniel D.; Tarjan, Robert Endre (1983), "A data structure for dynamic trees", Journal of Computer and System Sciences , 26 (3): 362–391, doi: 10.1016/0022-0000(83)90006-5 , MR   0710253
  3. 1 2 Harel, Dov; Tarjan, Robert E. (1984), "Fast algorithms for finding nearest common ancestors", SIAM Journal on Computing , 13 (2): 338–355, doi:10.1137/0213024
  4. ↑ Dietz, Paul F. (1991), "Finding level-ancestors in dynamic trees", Algorithms and data structures (Ottawa, ON, 1991), Lecture Notes in Computer Science, vol. 519, Berlin: Springer, pp. 32–40, doi:10.1007/BFb0028247, MR   1146687
  5. ↑ Klein, Philip N. (1998), "Computing the edit-distance between unrooted ordered trees", Algorithms—ESA '98 (Venice), Lecture Notes in Computer Science, vol. 1461, Berlin: Springer, pp. 91–102, doi:10.1007/3-540-68530-8_8, MR   1683332
  6. ↑ Demaine, Erik D.; Mozes, Shay; Rossman, Benjamin; Weimann, Oren (2010), "An optimal decomposition algorithm for tree edit distance", ACM Transactions on Algorithms, 6 (1): A2, doi:10.1007/978-3-540-73420-8_15, MR   2654906
  7. ↑ Buchsbaum, Adam L.; Westbrook, Jeffery R. (2000), "Maintaining hierarchical graph views", Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 2000), New York: ACM, pp. 566–575, MR   1755515
  8. ↑ Eppstein, David; Goodrich, Michael T. (2011), "Succinct greedy geometric routing using hyperbolic geometry", IEEE Transactions on Computers , 60 (11): 1571–1580, doi:10.1109/TC.2010.257, MR   2830035
  9. ↑ Duncan, Christian A.; Eppstein, David; Goodrich, Michael T.; Kobourov, Stephen G.; Nöllenburg, Martin (2013), "Drawing trees with perfect angular resolution and polynomial area", Discrete and Computational Geometry , 49 (2): 157–182, arXiv: 1009.0581 , doi:10.1007/s00454-012-9472-y, MR   3017904
  10. ↑ Alstrup, Stephen; Lauridsen, Peter W; Sommerlund, Peer; Thorup, Mikkel (1997), "Finding cores of limited length", Algorithms and Data Structures, Lecture Notes in Computer Science Volume, vol. 1272, Springer, pp. 45–54, doi:10.1007/3-540-63307-3_47
  11. ↑ Bille, Philip; Landau, Gad M.; Raman, Rajeev; Sadakane, Kunihiko; Satti, Srinivasa Rao; Weimann, Oren (2011), "Random access to grammar-compressed strings", Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA: SIAM, pp. 373–389, MR   2857133
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.