CODEWITHSUNDEEP
graph-theorypseudocode
sdadffdfd
sdadffdfd

Reputation: 693

The isomorphic subgraph problem

Let G be a graph and δ(G) the minimum degree of a vertex. Describe an algorithm in pseudocode that, for a given tree T with k<= δ(G) edges, should be build (in polinomial time) a sub-graph H of G so that H is isomorphic with T.

How do I even start ?

Upvotes: 1

Views: 313

Answers (3)

sdadffdfd
sdadffdfd

Reputation: 693

By knowing that T has δ(G) maximum edges I can start from any node in G , and build T in G by choosing any node because I will have always enough edges and vertexes. Complexity is O(n).

Upvotes: 0

philosodad
philosodad

Reputation: 1808

Well, you definitely need to start at a node of your graph that has at least as many neighbors as the root of your tree has children.

The answer depends a little bit on precisely what your professor means by k <= delta(G) edges. If he means what I think he means, that there are as many or fewer edges in the tree than there are neighbors of a 'peak' node, that simplifies things quite a bit. For one thing, it hints that you need to find a peak node. If he means by 'peak' a node that has a higher degree than any of it's neighbors, you might be able to discover a node like that by starting at a node and then choosing a neighbor of higher degree, repeat as needed.

Upvotes: 1

David Conde
David Conde

Reputation: 4637

The main issue here is the polynomial time, but to give you a starter, you should start on the root of your tree and in a node of your graph( i believe finding the node is one of the major challenges) and from that place you should build your tree.

Notice that any DFS or BFS type algorithms won't do the trick, because they're not polynomial

Hope I can help!

Upvotes: 0

Related Questions