Computing invariants in graphs of small bandwidth

André Pönitz

Mathematics and Computers in Simulation (MATCOM), 1999, vol. 49, issue 3, 179-191

Abstract: Many graph invariants (chromatic number, rook polynomial, Tutte polynomial, etc.) are known to be computable for general graphs in exponential time only. Algorithms for their computation usually depend on special properties of the invariants and are not extendable to slightly different problems.

Keywords: Chromatic polynomial; Recurrence relations; Composition method; Polynomial invariants (search for similar items in EconPapers)
Date: 1999
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037847549900052X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:matcom:v:49:y:1999:i:3:p:179-191

Access Statistics for this article

Mathematics and Computers in Simulation (MATCOM) is currently edited by Robert Beauwens

More articles in Mathematics and Computers in Simulation (MATCOM) from Elsevier
Bibliographic data for series maintained by Catherine Liu ().