English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We study the problems of finding a minimum cycle basis (a minimum-weight set of cycles that form a basis for the cycle space) and a minimum homology basis (a minimum-weight set of cycles that generates the 1-dimensional $(mathbb{  Z}_  2  )$-homology classes) of an undirected graph cellularly embedded on a surface. The problems are closely related, because the minimum cycle basis of a graph contains its minimum homology basis, and the minimum homology basis of the 1-skeleton of any graph is exactly its minimum cycle basis.For the minimum cycle basis problem, we give a deterministic $  O  (  n^  ω   + 2^{  2  g}   n^  2   +   m  )$-time algorithm for graphs cellularly embedded on an orientable surface of genus $  g$  . Prior to this work, the best known algorithms for surface-embedded graphs were those for general graphs: an $  O  (  m^  ω  )$-time Monte Carlo algorithm   and a deterministic $  O  (  nm^  2  /  log+   n^  2  m  )$-time algorithm  .For the minimum homology basis problem, we give a deterministic $  O  ((  g   +   b  )^  3  n  log+   m  )$-time algorithm for graphs cellularly embedded on an orientable or non-orientable surface of genus $  g$   with $  b$   boundary components, improving on existing algorithms for many values of $  g$   and $  n$  . The algorithm assumes that shortest paths are unique; this assumption can be avoided by either using random perturbations of the edge weights guaranteeing a high probability of success or by deterministic means at a cost of an $  O  (log)$ factor increase in running time.

Minimum cycle and homology bases of surface-embedded graphs