This paper is concerned with the subclass of graphs called cubic graphs. We survey these graphs and their history. Several classical graph theory results concerning cubic graphs are explained. Graph theory problems whose solutions on cubic graphs are particularly important or interesting are presented both from the sequential and parallel point of view. A new algorithm is presented for the maximal matching problem restricted to cubic graphs. Many miscellaneous facts about cubic graphs are also described. An extensive list of references is provided.
Cubic graphs / Greenlaw, R.; Petreschi, Rossella. - In: ACM COMPUTING SURVEYS. - ISSN 0360-0300. - STAMPA. - 27:4(1996), pp. 471-495.
Cubic graphs
PETRESCHI, Rossella
1996
Abstract
This paper is concerned with the subclass of graphs called cubic graphs. We survey these graphs and their history. Several classical graph theory results concerning cubic graphs are explained. Graph theory problems whose solutions on cubic graphs are particularly important or interesting are presented both from the sequential and parallel point of view. A new algorithm is presented for the maximal matching problem restricted to cubic graphs. Many miscellaneous facts about cubic graphs are also described. An extensive list of references is provided.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
