Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth

Details Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth

2009-02-10

arxiv.org/abs/0902.1693v4

Algorithmica, 61(1):3-35, 2011

Computer Science

Data Structures and Algorithms

v4: Minor error in Lemma 5.5 fixed, Section 6.6 added, minor improvements. 44 pages, 14 figures

Scientific paper

10.1007/s00453-010-9439-4

We consider the multivariate interlace polynomial introduced by Courcelle (2008), which generalizes several interlace polynomials defined by Arratia, Bollobas, and Sorkin (2004) and by Aigner and van der Holst (2004). We present an algorithm to evaluate the multivariate interlace polynomial of a graph with n vertices given a tree decomposition of the graph of width k. The best previously known result (Courcelle 2008) employs a general logical framework and leads to an algorithm with running time f(k)*n, where f(k) is doubly exponential in k. Analyzing the GF(2)-rank of adjacency matrices in the context of tree decompositions, we give a faster and more direct algorithm. Our algorithm uses 2^{3k^2+O(k)}*n arithmetic operations and can be efficiently implemented in parallel.

Affiliated with

Also associated with

No associations

Rating

Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-20348