Algorytmy oparte na nowym sposobie opisu wierzchołków grafu

• Autorzy: Schiff K.

Warianty tytułu

EN

Algorithms based on a new method of graph vertex description

• Języki publikacji: PL

Abstrakty

EN

The two new polynominal graph algorithms are presented in this article, first for graph isomorphism and the secend dor vertex coloring problem. Both are heuristic and used the new way in which the graph vertex are described.

Słowa kluczowe

PL

izomorfizm grafów; kolorowanie grafów; wierzchołki grafów

EN

graph isomorphism; graph coloring; graph vertices

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Czasopismo Techniczne. Elektrotechnika
• Rocznik: 2000
• Tom: R. 97, z. 4-E
• Strony: 12--25
• Opis fizyczny: Bibliogr. 15 poz., rys., tab.

Twórcy

autor

Schiff K.

Bibliografia

• [1] A.T. Berztiss, A backtrack procedure for isomorphism of directed graph, J.ACM 20, 1973, s.365-377.
• [2] L. Chen, Graph Isomorphism and Identification Matrices: Parallel Algorithms, IEEE Transaction on Parallel and Distributed Systems, vol7, no.3, 1996, s.308-319.
• [3] M.R. Garey, D.S. Johnson, Computer and intractability: A Guide to the Theory of NP-completeness, New York, 1979, s.285.
• [4] H.B. Mitall, A fast backtrack algorithm for graph isomorphism, Infor. Processing Lett., vol.29, 1988, s.105-110.
• [5] K. Schiff, Efektywność równoległych algorytmów grafowych, praca doktorska 1998, AGH, Wydz. EAiE.
• [6] D.C. Schmidt, L.E. Druffel, A fast backtrack algorithm to test directed graphs for isomorphism using distance matrices, J.ACM 23, 1976, s.433-445.
• [7] D.S. Seong, Y.K. Choi, H.S. Kim, K.H. Park, An algorithm for optimal isomorphism between two random graphs, Pattern Recognition Letters 15, 1994, s.321-327.
• [8] M.M. Sysło, N. Deo, J.S. Kowalik, Algorytmy optymalizacji dyskretnej z programami w języku Pascal, PWN, Warszawa 1993.
• [9] N. Christofides, Graph Theory. An Algorithmic Approach, Acad. Press, London 1975.
• [10] D.J.A. Welsh, M.B. Powell, An upper bound for the chromatic number of a graph and its application to timetabeling problem, Comput. J. 10, 1967, s.85-86.
• [11] D. Matul a, i in., Graph coloring algorithms, w Read R.C. (red.) Graph Theory and Computing, Academic Press, London 1972, s.109-122.
• [12] D. Brelaz, New methods to color the vertices of a graph, Communication ACM 22, 1979, s.251-256.
• [13] F.T. Leighton, A graph coloring algorithm for large scheduling problems, J. Res. Nat. Bur. Standards 84, 1979, s.489-506.
• [14] K. Schiff, Izomorfizm grafów nieskierowanych, Kwartalnik AGH Elektrotechnika, tom 17, zeszyt 2, 1998.
• [15] K. Schiff, Algorytm wyznaczania maksymalnej kliki grafu, Kwartalnik AGH Elektrotechnika, tom 17, zeszyt 4, 1998.