Even Faster Exact Bandwidth
| dc.creator | Cygan, Marek | |
| dc.creator | Pilipczuk, Marcin | |
| dc.date | 2009-02-10 | |
| dc.date.accessioned | 2026-07-07T12:39:53Z | |
| dc.date.available | 2026-07-07T12:39:53Z | |
| dc.description | We deal with exact algorithms for Bandwidth, a long studied NP-hard problem. For a long time nothing better than the trivial O*(n!) exhaustive search was known. In 2000, Feige an Kilian came up with a O*(10^n)-time algorithm. Recently we presented algorithm that runs in O*(5^n) time and O*(2^n) space.. In this paper we present a major modification to our algorithm which makes it run in O(4.83^n) time with the cost of O*(4^n) space complexity. This modification allowed us to perform Measure & Conquer analysis for the time complexity which was not used for such types of problems before. | |
| dc.description | Paper submitted to Transaction on Algorithms on 5th Nov 2008 | |
| dc.identifier | https://arxiv.org/abs/0902.1661 | |
| dc.identifier | http://arxiv.org/abs/0902.1661 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/219277 | |
| dc.subject | Computational Complexity | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Even Faster Exact Bandwidth | |
| dc.type | text |