Computing the Permanental Polynomial of Bipartite Graphs
ACM Communications in Computer Algebra · 01.12.2025 · 59 (4) · 116-120
DOI: 10.1145/3832046.3832058 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Communications in Computer Algebra, online erschienen am 18.08.2026. Verfasst von Surabhi Chakrabartty und 1 weiteren Autor:innen. Die Arbeit nennt 15 Literaturangaben.
Abstract (Originalsprache)
The computation of the permanental polynomial of a matrix is a well-known computationally hard problem, even for (0, 1)-matrices. We define a modified characteristic polynomial by altering the signs of certain coefficients in the characteristic polynomial, and show that the permanental polynomial can be expressed as a linear combination of modified characteristic polynomials of subgraphs obtained by successively removing vertex-disjoint 4 k -cycles.
Zitieren
APA
Chakrabartty, S., & Singh, R. (2025). Computing the Permanental Polynomial of Bipartite Graphs. ACM Communications in Computer Algebra, 59(4), 116-120. https://doi.org/10.1145/3832046.3832058
Vancouver
Chakrabartty S, Singh R. Computing the Permanental Polynomial of Bipartite Graphs. ACM Communications in Computer Algebra. 2025;59(4):116-120. doi:10.1145/3832046.3832058
BibTeX
@article{Chakrabartty2025,
author = {Chakrabartty, Surabhi and Singh, Ranveer},
title = {Computing the Permanental Polynomial of Bipartite Graphs},
journal = {ACM Communications in Computer Algebra},
year = {2025},
volume = {59},
number = {4},
pages = {116--120},
doi = {10.1145/3832046.3832058}
}
EUVIMED