<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees

Name: Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
Creator: Hans L. Boblaender
Keywords: 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences

descriptionPublicationkeyboard_double_arrow_right Article , Part of book or chapter of book 01 Jan 1988Publisher:Elsevier BVJournal:Journal of Algorithms, volume 11, pages 631-643 (issn: 0196-6774,

Authors: Hans L. Boblaender;

doi: 10.1016/0196-6774(90)90013-5 , 10.1007/3-540-19487-8_26

Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees

- Summary
- Metrics

Abstract

In this paper we show that Graph Isomorphism and Chromatic Index are solvable in polynomial time when restricted to the class of graphs with treewidth ≤k (k a constant) (or equivalently, the class of partial k-trees). Also, we show that there exist algorithms that find tree-decompositions with treewidth ≤k of graphs with treewidth ≤k, in O(n3) time, (k constant).

Related Organizations

Utrecht University
Netherlands
University Museum Utrecht
Netherlands

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	154
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 1%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%