Even faster exact bandwidth

DOI10.1145/2071379.2071387MaRDI QIDQ3189049zbMATH OpenOpenAlexFDO

Authors Marek Cygan, Marcin Pilipczuk

Publication date 9 September 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0902.1661

zbMATH Keywords

bandwidthexact algorithmsmeasure and conquer

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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.

Recommendations

• Faster Exact Bandwidth
• Exact and approximate bandwidth
• Exact and Approximate Bandwidth
• Bandwidth and distortion revisited
• An exponential time 2-approximation algorithm for bandwidth

Cited in

(16)

• Tractabilities and intractabilities on geometric intersection graphs
• New results on edge-bandwidth
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• Exact and Approximate Bandwidth
• An exponential time 2-approximation algorithm for bandwidth
• An exponential time 2-approximation algorithm for bandwidth
• Bandwidth and distortion revisited
• Exact algorithms for minimum weighted dominating induced matching
• A dual representation simulated annealing algorithm for the bandwidth minimization problem on graphs
• Faster Exact Bandwidth
• Exact and parameterized algorithms for window width minimization in bipartite arrangement
• Bandwidth parameterized by cluster vertex deletion number
• Bandwidth parameterized by cluster vertex deletion number
• Exact and approximate digraph bandwidth
• Exact and approximate bandwidth
• Exact and parameterized algorithms for window width minimization in bipartite arrangement

This page was built for publication: Even faster exact bandwidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3189049)