Advertisement
Published in:
01-08-2014
An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents
Published in: Theory of Computing Systems | Issue 2/2014
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
It is well known that permanents of matrices of bounded tree-width are efficiently computable. Here, the tree-width of a square matrix M=(m
ij
) with entries from a field \(\mathbb{K}\) is the tree-width of the underlying graph G
M
having an edge (i,j) if and only if the entry m
ij
≠0. Though G
M
is directed this does not influence the tree-width definition. Thus, it does not reflect the lacking symmetry when m
ij
≠0 but m
ji
=0. The latter however might have impact on the computation of the permanent.
In this paper we introduce and study an extended notion of tree-width for directed graphs called triangular tree-width. We give examples where the latter parameter is bounded whereas the former is not. As main result we show that permanents of matrices of bounded triangular tree-width are efficiently computable. This result is shown to hold as well for the Hamiltonian Cycle problem.