Plane Decompositions as Tools for Approximation

Details Plane Decompositions as Tools for Approximation Plane Decompositions as Tools for Approximation

2006-02-15

arxiv.org/abs/cs/0602057v1

Computer Science

Data Structures and Algorithms

Scientific paper

Tree decompositions were developed by Robertson and Seymour. Since then algorithms have been developed to solve intractable problems efficiently for graphs of bounded treewidth. 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.

Affiliated with

Also associated with

No associations

Rating

Plane Decompositions as Tools for Approximation 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 Plane Decompositions as Tools for Approximation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Plane Decompositions as Tools for Approximation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-254739