Geodesic
Computing Tutte Polynomials
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012), DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012) (2012).

Voir la notice de l'article provenant de la source Episciences

We present a new edge selection heuristic and vertex ordering heuristic that together enable one to compute the Tutte polynomial of much larger sparse graphs than was previously doable. As a specific example, we are able to compute the Tutte polynomial of the truncated icosahedron graph using our Maple implementation in under 4 minutes on a single CPU. This compares with a recent result of Haggard, Pearce and Royle whose special purpose C++ software took one week on 150 computers. 
@article{DMTCS_2012_special_263_a73,
     author = {Monagan, Michael},
     title = {Computing {Tutte} {Polynomials}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)},
     year = {2012},
     doi = {10.46298/dmtcs.3087},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3087/}
}
TY  - JOUR
AU  - Monagan, Michael
TI  - Computing Tutte Polynomials
JO  - Discrete mathematics & theoretical computer science
PY  - 2012
VL  - DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3087/
DO  - 10.46298/dmtcs.3087
LA  - en
ID  - DMTCS_2012_special_263_a73
ER  - 
%0 Journal Article
%A Monagan, Michael
%T Computing Tutte Polynomials
%J Discrete mathematics & theoretical computer science
%D 2012
%V DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3087/
%R 10.46298/dmtcs.3087
%G en
%F DMTCS_2012_special_263_a73
Monagan, Michael. Computing Tutte Polynomials. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012), DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012) (2012). doi : 10.46298/dmtcs.3087. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3087/

Cité par Sources :