Approximation Algorithms for Directed Width Parameters

Details Approximation Algorithms for Directed Width Parameters Approximation Algorithms for Directed Width Parameters

2011-07-25

arxiv.org/abs/1107.4824v1

Computer Science

Data Structures and Algorithms

Scientific paper

Treewidth of an undirected graph measures how close the graph is to being a tree. Several problems that are NP-hard on general graphs are solvable in polynomial time on graphs with bounded treewidth. Motivated by the success of treewidth, several directed analogues of treewidth have been introduced to measure the similarity of a directed graph to a directed acyclic graph (DAG). Directed treewidth, D-width, DAG-width, Kelly-width and directed pathwidth are some such parameters. In this paper, we present the first approximation algorithms for all these five directed width parameters. For directed treewidth and D-width we achieve an approximation factor of O(sqrt{logn}). For DAG-width, Kelly-width and directed pathwidth we achieve an O({\log}^{3/2}{n}) approximation factor. Our algorithms are constructive, i.e., they construct the decompositions associated with these parameters. The width of these decompositions are within the above mentioned factor of the corresponding optimal width.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-571689