Geodesic
A practical algorithm for the computation of the genus
Ars Mathematica Contemporanea, Tome 22 (2022) no. 4, article no. 01, 14 p.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

We describe a practical algorithm to compute the (oriented) genus of a graph, give results of the program implementing this algorithm, and compare the performance to existing algorithms. The aim of this algorithm is to be fast enough for many applications instead of focusing on the theoretical asymptotic complexity.Apart from the specific problem and the results, the article can also be seen as an example how some design principles used to carefully develop and implement standard backtracking algorithms can still result in very competitive programs.
DOI : 10.26493/1855-3974.2320.c2d
Keywords: Genus, NP-complete, backtracking 
@article{10_26493_1855_3974_2320_c2d,
     author = {Gunnar Brinkmann},
     title = {A practical algorithm for the computation of the genus},
     journal = {Ars Mathematica Contemporanea},
     eid = {01},
     publisher = {mathdoc},
     volume = {22},
     number = {4},
     year = {2022},
     doi = {10.26493/1855-3974.2320.c2d},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2320.c2d/}
}
TY  - JOUR
AU  - Gunnar Brinkmann
TI  - A practical algorithm for the computation of the genus
JO  - Ars Mathematica Contemporanea
PY  - 2022
VL  - 22
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2320.c2d/
DO  - 10.26493/1855-3974.2320.c2d
LA  - en
ID  - 10_26493_1855_3974_2320_c2d
ER  - 
%0 Journal Article
%A Gunnar Brinkmann
%T A practical algorithm for the computation of the genus
%J Ars Mathematica Contemporanea
%D 2022
%V 22
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2320.c2d/
%R 10.26493/1855-3974.2320.c2d
%G en
%F 10_26493_1855_3974_2320_c2d
Gunnar Brinkmann. A practical algorithm for the computation of the genus. Ars Mathematica Contemporanea, Tome 22 (2022) no. 4, article  no. 01, 14 p. doi : 10.26493/1855-3974.2320.c2d. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2320.c2d/

Cité par Sources :