File Properties.h

↰ Parent directory (ADS/graph)

Properties of a GRAPH and of its trees, decided or measured by the visits of section 9.5:

Definition (ADS/graph/Properties.h)

Detailed Description

  • isTree(), whether an unoriented graph is a free tree: connected and with n - 1 edges, by a visit from any node, O( n + m );

  • diameter(), the largest distance in edges between two nodes, by a visit in breadth from each node, O( n ( n + m ) ); for an unoriented graph the matrix product of Seidel gives all the distances in :math:` O( n^{omega} log n ) `, iFUB of Crescenzi et al. finds the diameter of most real graphs with few visits, and on an unoriented graph one visit from any node u gives it within a factor 2, the eccentricity e( u ) <= D <= 2 e( u );

  • treeDiameter(), the diameter of a free tree by two visits, O( n ): the node farthest from any node is an end of a longest path, and the node farthest from it is the other end (the double sweep, proved by Bulterman et al.); and that of a binary tree with its height, in a postvisit: the longest path within a subtree or through the root, ( hl + 1 ) + ( hr + 1 ), O( n );

  • countTriangles(), the triangles of an unoriented graph by the ordering of Chiba and Nishizeki: each edge goes from the end of smaller degree (ties by name) to the other, and each triangle is counted once, at its first node, as an edge between two of its out-neighbours. Each node has :math:` O( sqrt{m} ) ` out-neighbours, so the time is :math:` O( m sqrt{m} ) , against :math: O( m n ) ` for the merge of the lists of the ends of each edge and :math:` Theta( n^3 ) ` on the matrix; the product of matrices of Itai and Rodeh takes :math:` O( n^{omega} ) `;

  • twoColoring(), a colouring 0 / 1 of the nodes of an unoriented graph with the ends of each edge apart, or nothing if there is none: by the theorem of Koenig, if and only if there is no odd cycle, which the visit in breadth from each node not coloured finds as an edge between two nodes of the same level parity, O( n + m ) (the twoColoring() of File EasyCases.h takes a matrix of adjacency, in :math:` Theta( n^2 ) `);

  • universalSink(), the node of an oriented graph with an edge from every other node and no edge out, NIL if there is none, from the matrix of adjacency in :math:` Theta( n ) ` entries read out of the :math:` n^2 `, by the elimination of King and Smith-Thomas: the entry ( c , j ) rules out c (an edge out) or j (an edge missing in), so one scan leaves one candidate, checked on its row and its column, at most 3 ( n - 1 ) entries;

  • uniqueTopologicalOrder(), the topological order of an oriented graph if it is the only one, nothing if there is a cycle or more orders: by the algorithm of Kahn, the order is unique if and only if the set of the nodes with no entering edge never has two of them, i.e., if and only if every two consecutive nodes of the order are joined by an edge, a Hamiltonian path, O( n + m );

  • treeVertexCover(), a minimum vertex cover of a forest, the fewest nodes that touch every edge: by the greedy on the leaves, the parent of a leaf taken (a cover has the leaf or its parent, and the parent covers more), on the nodes in the reverse order of a visit in breadth, O( n ). The complement is a maximum independent set. A vertex cover is NP-hard on general graphs (chapter 18), and on a tree with weights on the nodes a dynamic programming on the subtrees, with the root taken or not, solves it in O( n ).

The contracts [see File Contract.h]: isTree(), countTriangles(), twoColoring() and treeVertexCover() need an unoriented graph, the last one acyclic (checked by its visit); diameter() a node and every node reaching all the others, treeDiameter() a free tree; uniqueTopologicalOrder() an oriented graph; universalSink() a square matrix. At the level of the audits, twoColoring() ensures that its colouring is proper, uniqueTopologicalOrder() that its order is topological, and treeVertexCover() that its nodes cover the edges. The functions are defined in Properties.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, sections 9.5 and 18, https://algoritmicamente.it/materiali/libro/capitoli/cap09.pdf

  1. Konig, Grafok es matrixok, Matematikai es Fizikai Lapok 38, 116-119, 1931

  1. Seidel, On the all-pairs-shortest-path problem in unweighted undirected graphs, Journal of Computer and System Sciences 51(3), 400-403, 1995, doi:10.1006/jcss.1995.1078

  1. Crescenzi, R. Grossi, M. Habib, L. Lanzi, A. Marino, On computing the diameter of real-world undirected graphs, Theoretical Computer Science 514, 84-95, 2013, doi:10.1016/j.tcs.2012.09.018

    1. Bulterman, F. W. van der Sommen, G. Zwaan, T. Verhoeff, A. J. M. van Gasteren, W. H. J. Feijen, On computing a longest path in a tree, Information Processing Letters 81(2), 93-96, 2002, doi:10.1016/S0020-0190(01)00198-3

  1. Chiba, T. Nishizeki, Arboricity and subgraph listing algorithms, SIAM Journal on Computing 14(1), 210-223, 1985, doi:10.1137/0214017

  1. Itai, M. Rodeh, Finding a minimum circuit in a graph, SIAM Journal on Computing 7(4), 413-423, 1978, doi:10.1137/0207033

    1. King, B. Smith-Thomas, An optimal algorithm for sink-finding, Information Processing Letters 14(3), 109-111, 1982, doi:10.1016/0020-0190(82)90065-6

    1. Kahn, Topological sorting of large networks, Communications of the ACM 5(11), 558-562, 1962, doi:10.1145/368996.369025

    1. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, 85-103, 1972, doi:10.1007/978-1-4684-2001-2_9

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions