Leveling the Grid

Lade...
Vorschaubild
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2013
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
ArXiv-ID
Internationale Patentnummer
EU-Projektnummer
DFG-Projektnummer
Forschungsförderung
Projekt
Open Access-Veröffentlichung
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
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
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