Leveling the Grid

Publikationstyp: Beitrag zu einer Konferenz
Autor/innen: Cornelsen, Sabine; Karrenbauer, Andreas; Li, Shujun
Erscheinungsjahr: 2013
Erschienen in: 2012 Proceedings of the Fourteenth Workshop on Algorithm Engineering and Experiments (ALENEX) / Bader, David A.; Mutzel, Dort (Hrsg.). - Philadelphia, PA : Society for Industrial and Applied Mathematics, 2013. - S. 45-54. - ISBN 978-1-61197-212-2
DOI (zitierfähiger Link): https://dx.doi.org/10.1137/1.9781611972924.4
Zusammenfassung:
Motivated by an application in image processing, we introduce the grid-leveling 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) min-cost ow algorithm for networks that, after removing one node, are planar, have bounded degrees, and have bounded capacities. The costs may be arbitrary.
Fachgebiet (DDC): 004 Informatik
Link zur Lizenz: Deposit-Lizenz
Universitätsbibliographie: Ja

Zitieren

Dateien zu dieser Ressource

Dateien Größe Format Anzeige

Zu diesem Dokument gibt es keine Dateien.

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. 45-54. ISBN 978-1-61197-212-2. Available under: doi: 10.1137/1.9781611972924.4

@inproceedings{Cornelsen2013-12-18Level-19252, title={Leveling the Grid}, year={2013}, doi={10.1137/1.9781611972924.4}, isbn={978-1-61197-212-2}, address={Philadelphia, PA}, publisher={Society for Industrial and Applied Mathematics}, booktitle={2012 Proceedings of the Fourteenth Workshop on Algorithm Engineering and Experiments (ALENEX)}, pages={45--54}, editor={Bader, David A. and Mutzel, Dort}, author={Cornelsen, Sabine and Karrenbauer, Andreas and Li, Shujun} }

Leveling the Grid 2013-12-18 eng Karrenbauer, Andreas deposit-license 2012-05-09T09:12:52Z Motivated by an application in image processing, we introduce the grid-leveling 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) min-cost ow algorithm for networks that, after removing one node, are planar, have bounded degrees, and have bounded capacities. The costs may be arbitrary. Li, Shujun Publ. in: ALENEX12 : Proceedings of the Meeting on Algorithm Engineering & Experiments ; January 16, 2012, Kyoto, Japan / Society for Industrial and Applied Mathematics. - 2012. - pp. 45-54. - ISBN 978-1-611972-12-2 Karrenbauer, Andreas Cornelsen, Sabine Cornelsen, Sabine 2012-05-09T09:12:52Z Li, Shujun

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto