7
votes
0answers
90 views

Algorithms for computing the Resilience of Graphs

The definition of resilience with a graph $G$ w.r.t to a monotone property $\mathcal{P}$ is well known. (Global resilience) Let $\mathcal{P}$ be an increasing monotone property. The global ...
0
votes
1answer
124 views

Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...
2
votes
1answer
376 views

Suppose the independent number of a graph is bounded. How small the clique number can be?

Suppose the independent number of a graph is bounded. How small the clique number can be? linear? It seems to be a natural problem to ask. but I could not find any reference. Thanks.