Geodesic
Representing polynomial of ST-CONNECTIVITY
Discrete mathematics & theoretical computer science, Tome 25 (2023-2024) no. 2 Cet article a éte moissonné depuis la source Episciences

Voir la notice de l'article

We show that the coefficients of the representing polynomial of any monotone Boolean function are the values of the M\"obius function of an atomistic lattice related to this function. Using this we determine the representing polynomial of any Boolean function corresponding to a ST-CONNECTIVITY problem in acyclic quivers (directed acyclic multigraphs). Only monomials corresponding to unions of paths have non-zero coefficients which are $(-1)^D$ where $D$ is an easily computable function of the quiver corresponding to the monomial (it is the number of plane regions in the case of planar graphs). We determine that the number of monomials with non-zero coefficients for the two-dimensional $n \times n$ grid connectivity problem is $2^{\Omega(n^2)}$.
DOI : 10.46298/dmtcs.9934
Classification : 06E30, 68-XX 
@article{DMTCS_2024_25_2_a17,
     author = {Iraids, J\={a}nis and Smotrovs, Juris},
     title = {Representing polynomial of {ST-CONNECTIVITY}},
     journal = {Discrete mathematics & theoretical computer science},
     year = {2023-2024},
     volume = {25},
     number = {2},
     doi = {10.46298/dmtcs.9934},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.9934/}
}
TY  - JOUR
AU  - Iraids, Jānis
AU  - Smotrovs, Juris
TI  - Representing polynomial of ST-CONNECTIVITY
JO  - Discrete mathematics & theoretical computer science
PY  - 2023-2024
VL  - 25
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.9934/
DO  - 10.46298/dmtcs.9934
LA  - en
ID  - DMTCS_2024_25_2_a17
ER  - 
%0 Journal Article
%A Iraids, Jānis
%A Smotrovs, Juris
%T Representing polynomial of ST-CONNECTIVITY
%J Discrete mathematics & theoretical computer science
%D 2023-2024
%V 25
%N 2
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.9934/
%R 10.46298/dmtcs.9934
%G en
%F DMTCS_2024_25_2_a17
Iraids, Jānis; Smotrovs, Juris. Representing polynomial of ST-CONNECTIVITY. Discrete mathematics & theoretical computer science, Tome 25 (2023-2024) no. 2. doi: 10.46298/dmtcs.9934

Cité par Sources :