This article is cited in 3 papers

A linear algorithm for computing the multiclique cover number of a series-parallel graph

V. V. Lepin

Institute of Mathematics of the National Academy of Sciences of Belarus

Abstract: A multiclique is a complete multipartite subgraph of a graph. A multiclique cover of a graph $G$ is a collection of multicliques of $G$ whose edge sets cover the edge set of $G$ (every edge of $G$ belongs to at least one multiclique of the collection). The multiclique cover number, $mc(G)$, of a graph $G$ is the minimum number of multicliques in a multiclique cover of $G$. A linear-time algorithm for computing the multiclique cover number of a (simple) series-parallel graph is given.

UDC: 519.1

Received: 30.09.2008

Bibliographic databases:

•