All Questions
Tagged with algorithms extremal-graph-theory
7 questions
1
vote
1
answer
299
views
maximal sets of vertices that avoids a clique
I am looking for some known algorithm that finds, for a given graph, all the maximal sets of vertices that avoid a clique of some given size $k$. I'd prefer one written in MATLAB, but other languages ...
CommunityBot
- 1
2
votes
1
answer
252
views
Size of forbidden minors for treewidth
For any $k$, the class of graphs of treewidth at most $k$ can be characterized by a finite set of forbidden minors.
For treewidth $1$ and $2$, the set is of size $1$. Then for treewidth $3$, the set ...
- 32.1k
2
votes
1
answer
155
views
Combinatorial process on multisets of integers
Edit: I prefer to formulate first the problem as Fedor Petrov suggests in the comments:
We are given a multiset $F$, initially containing only the single integer $h$. Sequentially, at each time step, ...
- 1,677
3
votes
1
answer
305
views
Counting the forests obtainable by removing subtrees from binary trees
Let $B_h$ be the perfect binary tree having height $h$ (i.e. the binary tree with height $h$ in which all interior nodes have two children and all leaves have the same depth or same level).
For any ...
- 60.6k
0
votes
1
answer
431
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 ...
- 4,589
6
votes
0
answers
315
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 ...
- 903
2
votes
1
answer
482
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.
- 82.7k