Publikation:

Leveling the Grid

Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2013

Autor:innen

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
http://nbn-resolving.de/urn:nbn:de:bsz:352-192523
DOI (zitierfähiger Link)
https://doi.org/10.1137/1.9781611972924.4
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung

Sammlungen

Informatik und Informationswissenschaft: Publikationen
Zukunftskolleg: Publikationen
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen 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, 2013, pp. 45-54. ISBN 978-1-61197-212-2. Available under: doi: 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.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690CORNELSEN, 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, 2013, pp. 45-54. ISBN 978-1-61197-212-2. Available under: doi: 10.1137/1.9781611972924.4
BibTex
@inproceedings{Cornelsen2013-12-18Level-19252,
  year={2013},
  doi={10.1137/1.9781611972924.4},
  title={Leveling the Grid},
  isbn={978-1-61197-212-2},
  publisher={Society for Industrial and Applied Mathematics},
  address={Philadelphia, PA},
  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}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/19252">
    <dcterms:issued>2013-12-18</dcterms:issued>
    <dc:language>eng</dc:language>
    <dc:rights>terms-of-use</dc:rights>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2012-05-09T09:12:52Z</dc:date>
    <dc:creator>Li, Shujun</dc:creator>
    <dcterms:title>Leveling the Grid</dcterms:title>
    <dcterms:bibliographicCitation>Publ. in: ALENEX12 : Proceedings of the Meeting on Algorithm Engineering &amp; Experiments ; January 16, 2012, Kyoto, Japan / Society for Industrial and Applied Mathematics. - 2012. - pp. 45-54. - ISBN 978-1-611972-12-2</dcterms:bibliographicCitation>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2012-05-09T09:12:52Z</dcterms:available>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/19252"/>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dc:contributor>Karrenbauer, Andreas</dc:contributor>
    <dc:contributor>Cornelsen, Sabine</dc:contributor>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/52"/>
    <dc:contributor>Li, Shujun</dc:contributor>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/52"/>
    <dc:creator>Karrenbauer, Andreas</dc:creator>
    <dcterms:abstract xml:lang="eng">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.</dcterms:abstract>
    <dc:creator>Cornelsen, Sabine</dc:creator>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen