Abstrakt. Motiverad av ett nyligen resultat av Elberfeld, Jakoby och Tantau [EJT10] som visar att MSO egenskaper är Logspace beräknas på grafer av avgränsad trädbredd, anser vi komplexiteten i att beräkna bestämningsfaktorn för adjacency matrisen i en avgränsad trädbredd graf och som vårt huvudsakliga resultat visar att det är i Logspace. Det är viktigt att notera att determinanten varken är en MSO-fastighet eller räknar antalet lösningar för en MSO-predikat. Denna teknik ger Logspace algoritmer för att räkna antalet spännande arborescenser och regisserade Euler turer i avgränsade trädbredd digrafer. Vi demonstrerar några linjära algebraiska tillämpningar av den avgörande algoritmen genom att beskriva Logspace procedurer för det karakteristiska polynomet, kraften i en viktad avgränsad trädbreddskurva och genomförbarheten av ett system av linjära ekvationer där den underliggande bipartitkurvan har avgränsat trädbredden. Slutligen kompletterar vi våra övre gränser genom att bevisa L-hårdheten i problemen med att beräkna bestämningsfaktorn, och att driva en avgränsad trädbreddsmatris. Vi visar också GapL-hårdheten av Iterated Matrix Multiplikation där varje matris har avgränsat trädbredd.
För riktade (resp., oriktade) grafer med begränsad trädbredd kan antalet eulerska kretsar beräknas i logspace REF (resp.
Bounded Treewidth and Space-Efficient Linear Algebra
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}