Published on Nov 06, 2015
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.
More Seminar Topics:
Ethernet Passive Optical Networks,
Dynamic Synchronous Transfer Mode,
Dynamic Memory Allocation,
Dynamic Cache Management Technique,
DRM Software Radio,
Driving Optical Network Evolution,
Digital Video Editing,
Digital Light Processing,
Digital Audio Broadcasting,
Development of the Internet,
Design of 2-D Filters using a Parallel Processor Architecture,
Design and Analysis Of Algorithms,
Data Security in Local Network using Distributed Firewalls,
Conditional Access System,
Worldwide Inter operatibility for Microwave Access