A Constant Factor Approximation for Directed Feedback Vertex Set in Graphs of Bounded Genus
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911873450901504 |
|---|---|
| author | Sun, Hao |
| author_facet | Sun, Hao |
| contents | The minimum directed feedback vertex set problem consists in finding the minimum set of vertices that should be removed in order to make a directed graph acyclic. This is a well-known NP-hard optimization problem with applications in various fields, such as VLSI chip design, bioinformatics and transaction processing deadlock prevention and node-weighted network design. We show a constant factor approximation for the directed feedback vertex set problem in graphs of bounded genus. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_01026 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Constant Factor Approximation for Directed Feedback Vertex Set in Graphs of Bounded Genus Sun, Hao Data Structures and Algorithms Discrete Mathematics 68W25 F.2.2 The minimum directed feedback vertex set problem consists in finding the minimum set of vertices that should be removed in order to make a directed graph acyclic. This is a well-known NP-hard optimization problem with applications in various fields, such as VLSI chip design, bioinformatics and transaction processing deadlock prevention and node-weighted network design. We show a constant factor approximation for the directed feedback vertex set problem in graphs of bounded genus. |
| title | A Constant Factor Approximation for Directed Feedback Vertex Set in Graphs of Bounded Genus |
| topic | Data Structures and Algorithms Discrete Mathematics 68W25 F.2.2 |
| url | https://arxiv.org/abs/2311.01026 |