Combinatorial optimization of cycles and bases

MaRDI QIDQ2912388zbMATH OpenFDO

Authors Jeff Erickson

Publication date 14 September 2012

zbMATH Keywords

algorithmscomputational topologytopological graph theory

Mathematics Subject Classification ID

Abstract complexes in algebraic topology (55U05) Fundamental group, presentations, free differential calculus (57M05) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Review text

This is a survey of optimization algorithms in computational algebraic topology. The problems considered involve finding optimal representatives of single elements, and also optimal generating sets, in a homology group of a simplicial complex or a fundamental group of an orientable surface. The paper is well written and quite comprehensive, with almost 200 references to the literature.NEWLINENEWLINEFor the entire collection see [Zbl 1245.55001].

Recommendations

• Measuring and computing natural generators for homology groups
• Annotating simplices with a homology basis and its applications
• Greedy optimal homotopy and homology generators

Cited in

(7)

• A higher-dimensional homologically persistent skeleton
• A fixed parameter tractable approximation scheme for the optimal cut graph of a surface
• Embedding graphs into two-dimensional simplicial complexes
• An improved heuristic for computing short integral cycle bases
• scientific article; zbMATH DE number 7662167 (Why is no real title available?)
• Texture space optimization via harmonic map
• Finding a shortest non-zero path in group-labeled graphs

Describes a project that uses

Uses Software

• Homology

This page was built for publication: Combinatorial optimization of cycles and bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2912388)