An efficient parallel recognition algorithm of parity graphs

Autor:	E. Dahlhaus
Rok vydání:	2002
Předmět:	Discrete mathematics Combinatorics Analysis of parallel algorithms Computational complexity theory Cost efficiency Computer science Parallel algorithm Voltage graph Graph theory Recognition algorithm Parity (mathematics)
Zdroj:	ICCI
DOI:	10.1109/icci.1993.315399
Popis:	A parallel algorithm is developed which recognizes parity graphs in O(log/sup 2/ n) time using a linear number of processors. This improves previous results of G. Adhar and S. Peng (J. Algorithms, vol. 11, pp. 252-284, 1990) and of T. Przytycka and D. Corneil (J. Algorithms, vol. 12, pp. 96-109, 1991). >
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::2910111f1a8602bcd65eb0164f9b6872 https://doi.org/10.1109/icci.1993.315399 Zobrazit plný text záznamu