Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Graph Separators
Post: #1

Graph separation is a well-known 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 well-known NP-hard (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.

Important Note..!

If you are not satisfied with above reply ,..Please


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 page
Popular Searches: isopreference graph, frequency distribution graph, seminar on graph in ds, euro v aud graph, room separators curtains, teeth separators braces, cyclone separators design,

Quick Reply
Type your reply to this message here.

Image Verification
Image Verification
(case insensitive)
Please enter the text within the image on the left in to the text box below. This process is used to prevent automated posts.

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Malware Detection based on Dependency Graph using Hybrid Genetic Algorithm science projects buddy 0 1,028 28-12-2010 11:41 PM
Last Post: science projects buddy
  Planar Separators computer science crazy 0 656 08-04-2009 07:40 AM
Last Post: computer science crazy
  Graph seperater computer science crazy 0 915 22-09-2008 10:04 AM
Last Post: computer science crazy
  Planar Separators computer science crazy 0 978 22-09-2008 10:02 AM
Last Post: computer science crazy