Geodesic
Tropical Graph Parameters
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014) (2014).

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

Connection matrices for graph parameters with values in a field have been introduced by M. Freedman, L. Lovász and A. Schrijver (2007). Graph parameters with connection matrices of finite rank can be computed in polynomial time on graph classes of bounded tree-width. We introduce join matrices, a generalization of connection matrices, and allow graph parameters to take values in the tropical rings (max-plus algebras) over the real numbers. We show that rank-finiteness of join matrices implies that these graph parameters can be computed in polynomial time on graph classes of bounded clique-width. In the case of graph parameters with values in arbitrary commutative semirings, this remains true for graph classes of bounded linear clique-width. B. Godlin, T. Kotek and J.A. Makowsky (2008) showed that definability of a graph parameter in Monadic Second Order Logic implies rank finiteness. We also show that there are uncountably many integer valued graph parameters with connection matrices or join matricesof fixed finite rank. This shows that rank finiteness is a much weaker assumption than any definability assumption. 
@article{DMTCS_2014_special_265_a31,
     author = {Labai, Nadia and Makowsky, Johann},
     title = {Tropical {Graph} {Parameters}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014)},
     year = {2014},
     doi = {10.46298/dmtcs.2406},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2406/}
}
TY  - JOUR
AU  - Labai, Nadia
AU  - Makowsky, Johann
TI  - Tropical Graph Parameters
JO  - Discrete mathematics & theoretical computer science
PY  - 2014
VL  - DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2406/
DO  - 10.46298/dmtcs.2406
LA  - en
ID  - DMTCS_2014_special_265_a31
ER  - 
%0 Journal Article
%A Labai, Nadia
%A Makowsky, Johann
%T Tropical Graph Parameters
%J Discrete mathematics & theoretical computer science
%D 2014
%V DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2406/
%R 10.46298/dmtcs.2406
%G en
%F DMTCS_2014_special_265_a31
Labai, Nadia; Makowsky, Johann. Tropical Graph Parameters. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014) (2014). doi : 10.46298/dmtcs.2406. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2406/

Cité par Sources :