A practical algorithm for the computation of the genus - Brinkmann, Gunnar (Ars mathematica contemporanea, 2022)
Opišemo praktičen algoritem za izračun (orientabilnega) roda grafa, podamo rezultate programske implementacije tega algoritma in primerjamo njegovo izvedbo z izvedbo obstoječih algoritmov. Ta algoritem je namenjen temu, da je dovolj hiter za najrazličnejše primere, ne da bi se osredotočali na teoretično asimptotično kompleksnost. Poleg konkretnega problema in rezultatov, predstavljenih v članku, lahko članek razumemo tudi kot primer tega, da lahko nekatera oblikovalska načela, ki jih uporabimo za skrben razvoj in implementacijo standardnih algoritmov vračanja, prinesejo zelo konkurenčne programe.
Keywords: backtracking; genus; NP-complete; NP-poln; rod; vračanje