For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Computing the Invariant Polynomials of Graphs, Networks and Matroids
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2000/03/25
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
Category: Algorithms for Matroids and Related Discrete Systems
Tutte polynomial, matroid, simplicial complex, network reliability, BDD,
Full Text: PDF>>
The invariant polynomials of discrete systems such as graphs, matroids, hyperplane arrangements, and simplicial complexes, have been theoretically investigated actively in recent years. These invariants include the Tutte polynomial of a graph and a matroid, the chromatic polynomial of a graph, the network reliability of a network, the Jones polynomial of a link, the percolation function of a grid, etc. The computational complexity issues of computing these invariants have been studied and most of them are shown to be #P-complete. But, these complexity results do not imply that we cannot compute the invariants of a given instance of moderate size in practice. To meet large demand of computing these invariants in practice, there have been proposed a framework of computing the invariants by using the binary decision diagrams (BDD for short). This provides mildly exponential algorithms which are useful to solve moderate-size practical problems. This paper surveys the BDD-based approach to computing the invariants, together with some computational results showing the usefulness of the framework.