University of Surrey

Test tubes in the lab Research in the ATI Dance Research

Leveling the Grid

Cornelsen, S, Karrenbauer, A and Li, SJ (2012) Leveling the Grid In: 14th Workshop on Algorithm Engineering and Experiments (ALENEX 2012), 2012-01-16 - ?, Kyoto, Japan.

[img]
Preview
PDF
ALENEX2012.pdf
Available under License : See the attached licence file.

Download (229kB)
[img]
Preview
PDF (licence)
SRI_deposit_agreement.pdf

Download (33kB)

Abstract

Motivated by an application in image processing, we introduce the grid-leveling problem. It turns out to be the dual of a minimum cost flow problem for an apex graph with a grid graph as its basis. We present an O(n^{3/2}) algorithm for this problem. The optimum solution recovers missing DC coefficients from image and video coding by Discrete Cosine Transform used in popular standards like JPEG and MPEG. Generally, we prove that there is an O(n^{3/2}) min-cost flow algorithm for networks that, after removing one node, are planar, have bounded degrees, and have bounded capacities. The costs may be arbitrary.

Item Type: Conference or Workshop Item (Conference Paper)
Divisions : Faculty of Engineering and Physical Sciences > Computing Science
Authors :
AuthorsEmailORCID
Cornelsen, SUNSPECIFIEDUNSPECIFIED
Karrenbauer, AUNSPECIFIEDUNSPECIFIED
Li, SJUNSPECIFIEDUNSPECIFIED
Date : 2012
Contributors :
ContributionNameEmailORCID
PublisherSIAM, UNSPECIFIEDUNSPECIFIED
Related URLs :
Additional Information : Copyright 2012 Society for Industrial and Applied Mathematics
Depositing User : Symplectic Elements
Date Deposited : 24 Sep 2014 13:07
Last Modified : 24 Sep 2014 13:33
URI: http://epubs.surrey.ac.uk/id/eprint/532418

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year


Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800