Canonical labeling of graphs
- 1 January 1983
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 171-183
- https://doi.org/10.1145/800061.808746
Abstract
We announce an algebraic approach to the problem of assigning canonical forms to graphs. We compute canonical forms and the associated canonical labelings (or renumberings) in polynomial time for graphs of bounded valence, in moderately exponential, exp(n½ + &ogr;(1)),time for general graphs, in subexponential, nlog n, time for tournaments and for 2-(&ngr;,&kgr;,&lgr;) block designs with &kgr;,&lgr; bounded and nlog log n time for &lgr;-planes (symmetric designs) with &lgr; bounded. We prove some related problems NP-hard and indicate some open problems.Keywords
This publication has 0 references indexed in Scilit: