×

zbMATH — the first resource for mathematics

Computing the maximal canonical form for trees in polynomial time. (English) Zbl 1388.05035
Summary: Known algorithms computing a canonical form for trees in linear time use specialized canonical forms for trees and no canonical forms defined for all graphs. For a graph \(G=(V,E)\) the maximal canonical form is obtained by relabelling the vertices with \(1,\dots,|V|\) in a way that the binary number with \(|V|^2\) bits that is the result of concatenating the rows of the adjacency matrix is maximal. This maximal canonical form is not only defined for all graphs but even plays a special role among the canonical forms for graphs due to some nesting properties allowing orderly algorithms. We give an \(O(|V|^2)\) algorithm to compute the maximal canonical form of a tree.
MSC:
05C05 Trees
05C85 Graph algorithms (graph-theoretic aspects)
05C90 Applications of graph theory
92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)
Software:
GENREG
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Brinkmann, G, Fast generation of cubic graphs, J. Graph Theory, 23, 139-149, (1996) · Zbl 0858.05093
[2] Du, Z, Wiener indices of trees and monocyclic graphs with given bipartition, Int. J. Quantum Chem., 112, 1598-1605, (2012)
[3] I.A. Faradžev, Constructive enumeration of combinatorial objects, in Colloques Internationaux C.N.R.S. No260—Problèmes Combinatoires et Théorie des Graphes, (Orsay, 1976), pp. 131-135
[4] Grund, R, Konstruktion schlichter graphen mit gegebener gradpartition, Bayreuth. Math. Schriften, 44, 73-104, (1993) · Zbl 0785.05048
[5] G. Li, F. Ruskey, The advantages of forward thinking in generating rooted and free trees, in 100th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), (1999), pp. 939-940 · Zbl 0929.68091
[6] Meringer, M, Fast generation of regular graphs and construction of cages, J. Graph Theory, 30, 137-146, (1999) · Zbl 0918.05062
[7] R.C. Read (ed.), Graph Theory and Computing (Academic Press, New York, 1972)
[8] Read, RC, Every one a winner, Ann. Discrete Math., 2, 107-120, (1978) · Zbl 0392.05001
[9] Suzuki, M; Nagamochi, H; Akutsu, T, Efficient enumeration of monocyclic chemical graphs with given path frequencies, J. Cheminform., 6, 31, (2014)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.