Parallel algorithms for cographs recognition and applications. (English) Zbl 0765.68037
Algorithms and data structures, Proc. workshop WADS ’89, Ottawa/Canada 1989, Lect. Notes Comput. Sci. 382, 335-351 (1989).
Summary: [For the entire collection see Zbl 0753.00021.]
Cograph arise in such application areas as examination scheduling and automatic clustering of index terms. It is shown that recognition, transitive orientation, maximum node weighted clique, minimum node coloring, minimum weight dominating set, minimum fill-in and isomorphism for cographs is in NC. The model of computation in CRCW P-RAM.
Cograph arise in such application areas as examination scheduling and automatic clustering of index terms. It is shown that recognition, transitive orientation, maximum node weighted clique, minimum node coloring, minimum weight dominating set, minimum fill-in and isomorphism for cographs is in NC. The model of computation in CRCW P-RAM.
MSC:
| 68W15 | Distributed algorithms |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
