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.6 A Basis System of Problems

First let us introduce a few necessary notations.

An inequality of the form x′x″ between two 4-dimensional vectors x′, x″X will mean the validity of four inequalities x′ix″i, i =1,...,4. We say that vectors x, x ∈X are incomparable if neither x′x″ nor x′x″ holds.

We denote D(x′) images {xX| xX}, D+(x′) images {xX| xx′}, D (X′) imagesx∈X, D(x), D+(X′) imagesx∈X′ D+(x); X(I) images (T, ΔV, ΔV,C, ΔC,V).

Letter I will denote the set of all inputs of the CLC problem.

In the previous section eight CLC(x) problems for eight different values of the constraining vector x were analyzed. Yet we recall that in Section 12.4 an infinite family CLC(X) of CLC(x) problems over all possible vectors xX was defined. Does this mean that, once we have committed ourselves to obtaining the whole picture of complexity over all problems in CLC(X), we have to perform a similar complexity analysis for every CLC(x) problem from CLC(X)?

If this were so, it would be very unfortunate, ...

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