2010/04/28 by Marek Cygan, Marcin Pilipczuk, Cygan, Marek +1
Computer Science · Engineering · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1004.5012
openalex publication_date 2010/04/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we merge recent developments on exact algorithms for finding an ordering of vertices of a given graph that minimizes bandwidth (the BANDWIDTH problem) and for finding an embedding of a given graph into a line that minimizes distortion (the DISTORTION problem). For both problems we develop algorithms that work in O(9.363n) time and polynomial space. For BANDWIDTH, this improves O^*(10n) algorithm by Feige and Kilian from 2000, for DISTORTION this is the first polynomial space exact algorithm that works in O(cn) time we are aware of. As a byproduct, we enhance the O(5n+o(n))-time and O^*(2n)-space algorithm for DISTORTION by Fomin et al. to an algorithm working in O(4.383n) time and space.