Bandwidth and distortion revisited
Copyright policy )Bandwidth and distortion revisited
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.363^n) time and polynomial space. For BANDWIDTH, this improves O^*(10^n) algorithm by Feige and Kilian from 2000, for DISTORTION this is the first polynomial space exact algorithm that works in O(c^n) time we are aware of. As a byproduct, we enhance the O(5^{n+o(n)})-time and O^*(2^n)-space algorithm for DISTORTION by Fomin et al. to an algorithm working in O(4.383^n) time and space.
- University of Warsaw Poland
bandwidth, FOS: Computer and information sciences, exact algorithms, Distance in graphs, Applied Mathematics, Distortion, Graph labelling (graceful graphs, bandwidth, etc.), Bandwidth, Exponential algorithms, Graph algorithms (graph-theoretic aspects), Computer Science - Data Structures and Algorithms, Discrete Mathematics and Combinatorics, Data Structures and Algorithms (cs.DS), exponential algorithms, distortion, F.2.2, Exact algorithms
bandwidth, FOS: Computer and information sciences, exact algorithms, Distance in graphs, Applied Mathematics, Distortion, Graph labelling (graceful graphs, bandwidth, etc.), Bandwidth, Exponential algorithms, Graph algorithms (graph-theoretic aspects), Computer Science - Data Structures and Algorithms, Discrete Mathematics and Combinatorics, Data Structures and Algorithms (cs.DS), exponential algorithms, distortion, F.2.2, Exact algorithms
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).9 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!