Finding Induced Subgraphs via Minimal Triangulations

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

14 pages

Scientific paper

Potential maximal cliques and minimal separators are combinatorial objects which were introduced and studied in the realm of minimal triangulations problems including Minimum Fill-in and Treewidth. We discover unexpected applications of these notions to the field of moderate exponential algorithms. In particular, we show that given an n-vertex graph G together with its set of potential maximal cliques Pi_G, and an integer t, it is possible in time |Pi_G| * n^(O(t)) to find a maximum induced subgraph of treewidth t in G; and for a given graph F of treewidth t, to decide if G contains an induced subgraph isomorphic to F. Combined with an improved algorithm enumerating all potential maximal cliques in time O(1.734601^n), this yields that both problems are solvable in time 1.734601^n * n^(O(t)).

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Finding Induced Subgraphs via Minimal Triangulations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finding Induced Subgraphs via Minimal Triangulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding Induced Subgraphs via Minimal Triangulations will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-664632

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.