Computing $\vec{\mathcal{S}}$-DAGs and Parity Games
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911871399886848 |
|---|---|
| author | Hatzel, Meike Schröder, Johannes |
| author_facet | Hatzel, Meike Schröder, Johannes |
| contents | Treewidth on undirected graphs is known to have many algorithmic applications. When considering directed width-measures there are much less results on their deployment for algorithmic results. In 2022 the first author, Rabinovich and Wiederrecht introduced a new directed width measure, $\vec{\mathcal{S}}$-DAG-width, using directed separations and obtained a structural duality for it. In 2012 Berwanger~et~al.~solved Parity Games in polynomial time on digraphs of bounded DAG-width. With generalising this result to digraphs of bounded $\vec{\mathcal{S}}$-DAG-width and also providing an algorithm to compute the $\vec{\mathcal{S}}$-DAG-width of a given digraphs we give first algorithmical results for this new parameter. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_05571 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing $\vec{\mathcal{S}}$-DAGs and Parity Games Hatzel, Meike Schröder, Johannes Combinatorics Discrete Mathematics Treewidth on undirected graphs is known to have many algorithmic applications. When considering directed width-measures there are much less results on their deployment for algorithmic results. In 2022 the first author, Rabinovich and Wiederrecht introduced a new directed width measure, $\vec{\mathcal{S}}$-DAG-width, using directed separations and obtained a structural duality for it. In 2012 Berwanger~et~al.~solved Parity Games in polynomial time on digraphs of bounded DAG-width. With generalising this result to digraphs of bounded $\vec{\mathcal{S}}$-DAG-width and also providing an algorithm to compute the $\vec{\mathcal{S}}$-DAG-width of a given digraphs we give first algorithmical results for this new parameter. |
| title | Computing $\vec{\mathcal{S}}$-DAGs and Parity Games |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2405.05571 |