Graph Separators
computer science crazy Super Moderator Posts: 3,048 Joined: Dec 2008 
23092008, 12:48 AM
Graph separation is a wellknown tool to make (hard) graph problems accessible to a divide and conquer approach. We show how to use graph separator theorems in combination with (linear) problem kernels in order to develop fixed parameter algorithms for many wellknown NPhard (planar) graph problems. We coin the key notion of glueable select verify graph problems and derive from that a prospective way to easily check whether a planar graph problem will allow for a fixed parameter algorithm of running time for constant c. Besides, we introduce the novel concept of ``problem cores'' that might serve as an alternative to problem kernels for devising parameterized algorithms. One of the main contributions of the paper is to exactly compute the base c of the exponential term and its dependence on the various parameters specified by the employed separator theorem and the underlying graph problem. We discuss several strategies to improve on the involved constant c. Our findings also give rise to studying further refinements of the complexity class FPT of fixed parameter tractable problems. Use Search at http://topicideas.net/search.php wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion




Important Note..!
If you are not satisfied with above reply ,..PleaseASK HERE
So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this pagePossibly Related Threads...  
Thread  Author  Replies  Views  Last Post  
DYNAMIC GRAPH ALGORITHMS  seminar surveyer  0  1,418 
12012011, 11:54 AM Last Post: seminar surveyer 