Plane decompositions as tools for approximation

Show full item record

Title: Plane decompositions as tools for approximation
Author: Agnew, Melanie; Homan, Christopher
Abstract: Tree decompositions were developed by Robertson and Seymour [21]. Since then algorithms have been developed to solve intractable problems efficiently for graphs of bounded tree width. In this paper we extend tree decompositions to allow cycles to exist in the decomposition graph; we call these new decompositions plane decompositions because we require that the decomposition graph be planar. First, we give some background material about tree decompositions and an overview of algorithms both for decompositions and for approximations of planar graphs. Then, we give our plane decomposition definition and an algorithm that uses this decomposition to approximate the size of the maximum independent set of the underlying graph in polynomial time.
Description: arXiv.org article.
Record URI: http://hdl.handle.net/1850/9054
Date: 2008

Files in this item

Files Size Format View
MAgnewArticle02-01-2008.pdf 473.3Kb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML


Advanced Search

Browse