Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  A Riemann-Roch Theory for Sublattices of the Root Lattice A n, Graph Automorphisms and Counting Cycles in Graphs

Manjunath, M. (2011). A Riemann-Roch Theory for Sublattices of the Root Lattice A n, Graph Automorphisms and Counting Cycles in Graphs. PhD Thesis, Universität des Saarlandes, Saarbrücken.

Item is

Basisdaten

einblenden: ausblenden:
Genre: Hochschulschrift
Latex : A {R}iemann-{R}och Theory for Sublattices of the Root Lattice A n, Graph Automorphisms and Counting Cycles in Graphs

Externe Referenzen

einblenden:
ausblenden:
externe Referenz:
http://scidok.sulb.uni-saarland.de/volltexte/2012/4781/ (beliebiger Volltext)
Beschreibung:
-
OA-Status:
Grün
Beschreibung:
-
OA-Status:
Keine Angabe

Urheber

einblenden:
ausblenden:
 Urheber:
Manjunath, Madhusudan1, 2, Autor           
Mehlhorn, Kurt2, Ratgeber           
Haase, Christian3, Gutachter
Affiliations:
1International Max Planck Research School, MPI for Informatics, Max Planck Society, ou_1116551              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
3External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: This thesis consists of two independent parts. In the rst part of the thesis,
we develop a Riemann-Roch theory for sublattices of the root lattice An
extending the work of Baker and Norine (Advances in Mathematics, 215(2):
766-788, 2007) and study questions that arise from this theory. Our theory is
based on the study of critical points of a certain simplicial distance function
on a lattice and establishes connections between the Riemann-Roch theory and
the Voronoi diagrams of lattices under certain simplicial distance functions.
In particular, we provide a new geometric approach for the study of the
Laplacian of graphs. As a consequence, we obtain a geometric proof of the
Riemann-Roch theorem for graphs and generalise the result to other sub-lattices
of An. Furthermore, we use the geometric approach to study the problem of
computing the rank of a divisor on a finite multigraph G to obtain an algorithm
that runs in polynomial time for a fiixed
number of vertices, in particular with running time 2O(n log n)poly(size(G))
where n is the number of vertices of G. Motivated by this theory, we study a
dimensionality reduction approach to the graph automorphism problem and we also
obtain an algorithm for the related problem of counting automorphisms of graphs
that is based on exponential sums.
In the second part of the thesis, we develop an approach, based on
complex-valued hash functions, to count cycles in graphs in the data streaming
model. Our algorithm is based on the idea of computing instances of
complex-valued random variables over the given stream and improves drastically
upon the nave sampling algorithm.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2011-12-202011
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: Saarbrücken : Universität des Saarlandes
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: BibTex Citekey: ManjunathPhd2011
DOI: 10.22028/D291-26350
URN: urn:nbn:de:bsz:291-scidok-47818
Anderer: hdl:20.500.11880/26406
 Art des Abschluß: Doktorarbeit

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle

einblenden: