Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2011
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/1107.4824 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918514882772992 |
|---|---|
| author | Kintali, Shiva Kothari, Nishad Kumar, Akash |
| author_facet | Kintali, Shiva Kothari, Nishad Kumar, Akash |
| contents | Several problems that are NP-hard on general graphs are efficiently solvable on graphs with bounded treewidth. Efforts have been made to generalize treewidth and the related notion of pathwidth to digraphs. Directed treewidth, DAG-width and Kelly-width are some such notions which generalize treewidth, whereas directed pathwidth generalizes pathwidth. Each of these digraph width measures have an associated decomposition structure.
In this paper, we present approximation algorithms for all these digraph width parameters. In particular, we give an O(sqrt{logn})-approximation algorithm for directed treewidth, and an O({\log}^{3/2}{n})-approximation algorithm for directed pathwidth, DAG-width and Kelly-width. Our algorithms construct the corresponding decompositions whose widths are within the above mentioned approximation factors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1107_4824 |
| institution | arXiv |
| publishDate | 2011 |
| record_format | arxiv |
| spellingShingle | Approximation Algorithms for Digraph Width Parameters Kintali, Shiva Kothari, Nishad Kumar, Akash Data Structures and Algorithms Several problems that are NP-hard on general graphs are efficiently solvable on graphs with bounded treewidth. Efforts have been made to generalize treewidth and the related notion of pathwidth to digraphs. Directed treewidth, DAG-width and Kelly-width are some such notions which generalize treewidth, whereas directed pathwidth generalizes pathwidth. Each of these digraph width measures have an associated decomposition structure. In this paper, we present approximation algorithms for all these digraph width parameters. In particular, we give an O(sqrt{logn})-approximation algorithm for directed treewidth, and an O({\log}^{3/2}{n})-approximation algorithm for directed pathwidth, DAG-width and Kelly-width. Our algorithms construct the corresponding decompositions whose widths are within the above mentioned approximation factors. |
| title | Approximation Algorithms for Digraph Width Parameters |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/1107.4824 |