O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

12.4 A Parameterized Class of Subproblems of the CLC Problem

To perform the complexity analysis of the CLC problem, it is convenient to represent its input in the form of graph Ĝ = (V, C; E, EA) depicted in Figure 12.2. The set of vertices of this graph consists of two parts: V and C; set V will be referred to as the left part of graph Ĝ, while C will be called the right part. The set of edges will also consist of two parts: E and EA; the edges from E connect vertices in the left part, while the edges from EA connect parts V and C (i.e., constitute a bipartite subgraph of Ĝ); an edge (v, i) belongs to EA iff iA(v) (i.e., color i is admissible for vertex v).

The complexity of this problem will depend significantly on four parameters of graph Ĝ: T, ΔV, ΔV,C, ΔC,V.

images

Figure 12.2 Graph Ĝ defining an example of the CLC problem.

The first parameter T defines the type of graph G. We will distinguish between two types of graphs, depending on whether G is acyclic or not. Respectively, T will take only two values: 0 and ∞; T = 0 denotes the case of an acyclic graph G; otherwise T = ∞.

The second parameter ΔV denotes the maximum vertex degree of graph G (where we take into account only the edges from V to V).

The third parameter ΔV,C denotes the maximum vertex degree in V with respect to edges from EA. It corresponds to the maximum cardinality of lists A(v).

Finally, the fourth parameter ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required