Linear time canonicalization and enumeration of non-Isomorphic 1-Face embeddings

Marc Hellmuth, Anders S. Knudsen, Michal Kotrbík, Daniel Merkle, Nikolai Nøjgaard

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

Abstrakt

Antiparallel strong traces (ASTs) are a type of walks in graphs which use every edge exactly twice. They correspond to 1-face embeddings in orientable surfaces and can be used to design self-assembling protein or DNA strands. Based on a novel canonical form invariant for ASTs, gap vector, we provide a linear-time isomorphism test for ASTs and thus, also for orientable 1-face embeddings of graphs. Using the canonical form, we develop an algorithm for enumerating all pairwise non-isomorphic 1-face embeddings of graphs. We compare our algorithm with an independent implementation of a recent algebraic approach (Baši? et al., MATCH Commun. Math. Comput. Chem. 78 (3), 2017) on large data sets. Our results yield the first large-scale enumeration of non-isomorphic embeddings and investigation of their properties.

OriginalsprogEngelsk
Titel2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018
RedaktørerSuresh Venkatasubramanian, Rasmus Pagh
ForlagSociety for Industrial and Applied Mathematics Publications
Publikationsdato2018
Sider154-168
ISBN (Elektronisk)9781611975055
DOI
StatusUdgivet - 2018
Begivenhed20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018 - New Orleans, USA
Varighed: 7. jan. 20188. jan. 2018

Konference

Konference20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018
LandUSA
ByNew Orleans
Periode07/01/201808/01/2018

Fingeraftryk

Dyk ned i forskningsemnerne om 'Linear time canonicalization and enumeration of non-Isomorphic 1-Face embeddings'. Sammen danner de et unikt fingeraftryk.

Citationsformater