Type of Publication:  Contribution to a conference collection 
Author:  Cornelsen, Sabine; Karrenbauer, Andreas; Li, Shujun 
Year of publication:  2013 
Published in:  2012 Proceedings of the Fourteenth Workshop on Algorithm Engineering and Experiments (ALENEX) / Bader, David A.; Mutzel, Dort (ed.).  Philadelphia, PA : Society for Industrial and Applied Mathematics, 2013.  pp. 4554.  ISBN 9781611972122 
DOI (citable link):  https://dx.doi.org/10.1137/1.9781611972924.4 
Summary: 
Motivated by an application in image processing, we introduce the gridleveling problem. It turns out to be the dual of a minimum cost ow problem for an apex graph with a grid graph as its basis. We present an O(n3=2) algorithm for this problem. The optimum solution recovers missing DC coe cients 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(n3=2) mincost ow algorithm for networks that, after removing one node, are planar, have bounded degrees, and have bounded capacities. The costs may be arbitrary.

Subject (DDC):  004 Computer Science 
Bibliography of Konstanz:  Yes 
Files  Size  Format  View 

There are no files associated with this item. 
CORNELSEN, Sabine, Andreas KARRENBAUER, Shujun LI, 2013. Leveling the Grid. In: BADER, David A., ed., Dort MUTZEL, ed.. 2012 Proceedings of the Fourteenth Workshop on Algorithm Engineering and Experiments (ALENEX). Philadelphia, PA:Society for Industrial and Applied Mathematics, pp. 4554. ISBN 9781611972122. Available under: doi: 10.1137/1.9781611972924.4
@inproceedings{Cornelsen20131218Level19252, title={Leveling the Grid}, year={2013}, doi={10.1137/1.9781611972924.4}, isbn={9781611972122}, address={Philadelphia, PA}, publisher={Society for Industrial and Applied Mathematics}, booktitle={2012 Proceedings of the Fourteenth Workshop on Algorithm Engineering and Experiments (ALENEX)}, pages={4554}, editor={Bader, David A. and Mutzel, Dort}, author={Cornelsen, Sabine and Karrenbauer, Andreas and Li, Shujun} }