Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.03.2015 | Original Paper | Ausgabe 1-2/2015

Applicable Algebra in Engineering, Communication and Computing 1-2/2015

Searching combinatorial optimality using graph-based homology information

Zeitschrift:
Applicable Algebra in Engineering, Communication and Computing > Ausgabe 1-2/2015
Autoren:
Pedro Real, Helena Molina-Abril, Aldo Gonzalez-Lorenzo, Alexandra Bac, Jean-Luc Mari
Wichtige Hinweise
The first two authors are partially supported by FEDER funds via the research projects FQM-296 from JJAA (Junta de Andalucía) and MTM2009-12716 from MICINN (Spain).

Abstract

This paper analyses the topological information of a digital object \(O\) under a combined combinatorial-algebraic point of view. Working with a topology-preserving cellularization \(K(O)\) of the object, algebraic and combinatorial tools are jointly used. The combinatorial entities used here are vector fields, \(V\)-paths and directed graphs. In the algebraic side, chain complexes with extra \(2\)-nilpotent operators are considered. By mixing these two perspectives we are able to explore the problems of combinatorial and homological optimality. Combinatorial optimality is understood here as the problem for constructing a discrete gradient vector field (DGVF) in the sense of Discrete Morse Theory, such that it has the least possible number of critical cells. Fixing \({\mathbb {Z}}/2{\mathbb {Z}}\) as field of coefficients, by homological ‘optimality’ we mean the problem of constructing a \(2\)-nilpotent codifferential map \(\phi :C_*(K(O)) \rightarrow C_{*+1}(K(O))\) for finite linear combinations of cells in \(K(O)\), called homology integral operator. The homology groups associated to the chain complex \((C(K(O)), \phi )\) are isomorphic to those of \((C(K(O)), \partial )\), being \(\partial \) the canonical boundary or differential operator of the cell complex \(K(O)\). Relations between these two problems are tackled here by using a type of discrete graphs associated to a homology integral operator, called Homological Spanning Forests (HSF for short). Informally, an HSF for a cell complex can be seen as a kind of combinatorial compressed representation of a homology integral operator. As main result, we refine the heuristic for computing DGVFs based on the iterative Morse complex reduction technique of [1], reducing the search space for an optimal DGVF to an HSF associated to a homology integral operator.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 1-2/2015

Applicable Algebra in Engineering, Communication and Computing 1-2/2015 Zur Ausgabe

Editorial

Editorial

Premium Partner

    Bildnachweise