Smallest-last ordering and clustering and graph coloring algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Smallest-last ordering and clustering and graph coloring algorithms

Full text

Pdf (650 KB)

Source

Journal of the ACM (JACM) archive
Volume 30 , Issue 3 (July 1983) table of contents

Pages: 417 - 427

Year of Publication: 1983

ISSN:0004-5411

Authors

David W. Matula	Department of Computer Science, Southern Methodist University, Dallas, TX
Leland L. Beck	San Diego State University, San Diego, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 107, Citation Count: 24

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/2402.322385 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Daniel Brélaz, New methods to color the vertices of a graph, Communications of the ACM, v.22 n.4, p.251-256, April 1979 [doi>10.1145/359094.359101]
	2	FINCK, H.J, AND SACHS, H. Uber eme von H. S Wdf angegebene Schrenke fur de chromatische Za/d endlicher Graphen. Math Nachr. 39 (1969), 373-386
	3	M. R. Garey , D. S. Johnson, The Complexity of Near-Optimal Graph Coloring, Journal of the ACM (JACM), v.23 n.1, p.43-49, Jan. 1976 [doi>10.1145/321921.321926]
	4	GAREY, M R., JOHNSON, D.S, AN-O SO, H C. An application of graph coloring to printed circutt testing IEEE Orc. Syst 23 (1976), 591-599
	5	GRIMMETT, (3 R., AND MCDIARMID, C.J.H.On coloring random graphs. Math. Proc. Camb. Phd Soc. 77 (1975), 313-324.
	6	HARARY, F. Graph Theory. Addison-Wesley, Reading, Mass, 1969.
	7	JARDINE, N., AND SIBSON, R. Mathemattcal Taxonomy. Wdey, London, 1971.
	8	KARP, R.M. Reducab,lity among combinatorial problems. In Complexity of Computer Computations, R E. Mdler and J.W. Thatcher, Eds., Plenum, New York, 1972, pp. 85-103.
	9	KARP, R M.The fast approxtmate solution of hard combinatorial problems, Proc. 6th Southeastern Conf. on Combmatoncs, Graph Theory and Computing, Utilities Mathematiea, Winnipeg, 1975, pp 15-31
	10	LICK, D.R, Ah-O Wmax, A T. &degenerate graphs Canad d. Math. 22 (1970), 1082-1096.
	11	LinG, R.F. On the theory and construction of k-clusters. Comput. d. 15 (1972), 326-332.
	12	MATULAA, D.W A MIN-max theorem for graphs with applwatton to graph coloring. SIAM Rev. 10 (1968), 481-482.
	13	MATULA, D.W k-components, clusters and sllcmgs in graphs, SIAM Z ApgL Math. 22 (1972), 459-480.
	14	MATISLA, D.W Bounded color functions on graphs. Networks 2 (1972), 29-44.
	15	MATULA, D.W Graph theoretic techniques for cluster analysts algorithms. In Classification and Clustenng, J. Van Ryzm, Ed., Academic Press, New York, 1977, pp. 95-129,
	16	MATULA, D W. Subgraph connectwny numbers of a graph In Theory and Applications of Graphs, Lecture Notes m Mathematics 642, Y Alaw and D R. Lick, Eds, Springer.Verlag, New York, 1978, pp 371-383.
	17	MATULA, D W., MARBLE, G, AND ISAACSON, J D. Graph coloring algorithms. In Graph Theory and Computing, R C Read, Ed., Academic Press, New York, 1972, pp. 109-122.
	18	David W. Matula , Yossi Shiloach , Robert E. Tarjan, Two linear-time algorithms for five-coloring a planar graph, Stanford University, Stanford, CA, 1980
	19	StArER, P B.Graph-theoreac clustering of transaction flows. An application to the 1967 Umted States Intenndustnal Transacaons Table. Regional Research Institute Report, Dep. of Statistics and Computer Soene~, West Vtrginia Umv, 1974.
	20	Sneath, P H.A. A comparison of dtfferent clustering methods as applted to randomly-spaced points. Classificatwn Soc. Bull 1 (1966), 2-I8.
	21	SIqEATH, P.H A., AND SOKAL, R.R Numerical Taxonomy. Freeman, San Francisco, 1973.
	22	SZEKERE, G., AND WlLF, H.S.An mequal~ty for the chromatic number of a graph. J Combinatorial Theory 4 (1968), 1-3.

CITED BY 24

	Ewa Malesińska, An optimization method for the channel assignment in mixed environments, Proceedings of the 1st annual international conference on Mobile computing and networking, p.210-217, November 13-15, 1995, Berkeley, California, United States
	Albert Gräf , Thomas McKenney, Ensemble planning for digital audio broadcasting, Handbook of wireless networks and mobile computing, John Wiley & Sons, Inc., New York, NY, 2002
	Noga Alon , Raphael Yuster , Uri Zwick, Color-coding, Journal of the ACM (JACM), v.42 n.4, p.844-856, July 1995
	Magnús M. Halldórsson , Márió Szegedy, Lower bounds for on-line graph coloring, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.211-216, September 1992, Orlando, Florida, United States
	Thomas F. Coleman , Burton S. Garbow , Jorge J. Moré, Software for estimating sparse Hessian matrices, ACM Transactions on Mathematical Software (TOMS), v.11 n.4, p.363-377, Dec. 1985
	Thomas F. Coleman , Burton S. Garbow , Jorge J. More, Software for estimating sparse Jacobian matrices, ACM Transactions on Mathematical Software (TOMS), v.10 n.3, p.329-345, Sept. 1984
	Preston Briggs , Keith D. Cooper , Linda Torczon, Improvements to graph coloring register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.428-455, May 1994
	Amir Ben-Dor , Tzvika Hartman , Benno Schwikowski , Roded Sharan , Zohar Yakhini, Towards optimally multiplexed applications of universal DNA tag systems, Proceedings of the seventh annual international conference on Research in computational molecular biology, p.48-56, April 10-14, 2003, Berlin, Germany
	Noga Alon , Raphy Yuster , Uri Zwick, Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.326-335, May 23-25, 1994, Montreal, Quebec, Canada
	Peng-Jun Wan , Xiang-Yang Li , Ophir Frieder, OVSF-CDMA code assignment in wireless ad hoc networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA
	David Eppstein, All maximal independent sets and dynamic dominance for sparse graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Yonatan Aumann , Efrat Manisterski , Zohar Yakhini, Designing optimally multiplexed SNP genotyping assays, Journal of Computer and System Sciences, v.70 n.3, p.399-417, May 2005
	Marc Demange , Tinaz Ekim , Dominique de Werra, (p, k)-coloring problems in line graphs, Theoretical Computer Science, v.349 n.3, p.462-474, 16 December 2005
	Frank Dopatka , Roland Wismüller, Achieving realtime capabilities in ethernet networks by edge-coloring of communication conflict-multigraphs, Proceedings of the 24th IASTED international conference on Parallel and distributed computing and networks, p.180-185, February 14-16, 2006, Innsbruck, Austria
	Akshay Vashist , Casimir A. Kulikowski , Ilya Muchnik, Ortholog Clustering on a Multipartite Graph, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.4 n.1, p.17-27, January 2007
	Philip Brisk , Ajay Kumar Verma , Paolo Ienne, An optimistic and conservative register assignment heuristic for chordal graphs, Proceedings of the 2007 international conference on Compilers, architecture, and synthesis for embedded systems, September 30-October 03, 2007, Salzburg, Austria
	Philip Brisk , Ajay K. Verma , Paolo Ienne, Optimal polynomial-time interprocedural register allocation for high-level synthesis and ASIP design, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
	Reza Mahjourian , Feng Chen , Ravi Tiwari , My Thai , Hongqiang Zhai , Yuguang Fang, An approximation algorithm for conflict-aware broadcast scheduling in wireless ad hoc networks, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, May 26-30, 2008, Hong Kong, Hong Kong, China
	Jue Xue, Solving the Minimum Weighted Integer Coloring Problem, Computational Optimization and Applications, v.11 n.1, p.53-64, Oct. 1998
	B. Ries , D. de Werra, On two coloring problems in mixed graphs, European Journal of Combinatorics, v.29 n.3, p.712-725, April, 2008
	Rajeev Kumar , Paresh Tolay , Siddharth Tiwary, Enhancing solution quality of the biobjective graph coloring problem using hybridization of EA: biobjective graph coloring problem, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA
	Chih-Wei Yi, Maximum scan statistics and channel assignment problems in homogeneous wireless networks, Theoretical Computer Science, v.410 n.21-23, p.2223-2233, May, 2009
	Akihisa Kako , Takao Ono , Tomio Hirata , Magnús M. Halldórsson, Approximation algorithms for the weighted independent set problem in sparse graphs, Discrete Applied Mathematics, v.157 n.4, p.617-626, February, 2009
	Peng-Jun Wan , Scott C.-H. Huang , Lixin Wang , Zhiyuan Wan , Xiaohua Jia, Minimum-latency aggregation scheduling in multihop wireless networks, Proceedings of the tenth ACM international symposium on Mobile ad hoc networking and computing, May 18-21, 2009, New Orleans, LA, USA