Results 181 to 190 of about 367 (238)

Algorithms for the Multicolorings of Partial k-Trees

, 2002
Let each vertex v of a graph G have a positive integer weight ?(v). Then a multicoloring of G is to assign each vertex v a set of ?(v) colors so that any pair of adjacent vertices receive disjoint sets of colors. A partial k-tree is a graph with tree-width bounded by a fixed constant k.
Takehiro Ito, Takao Nishizeki, Xiao Zhou
openalex   +2 more sources

Generalized vertex-rankings of partial k-trees

, 1997
A c-vertex-ranking of a graph G for a positive integer c is a labeling of the vertices of G with integers such that, for any label i, deletion of all vertices with labels > i leaves connected components, each having at most c vertices with label i. We present a polynomial-time algorithm to find a c-vertex-ranking of a partial k-tree using the minimum ...
Md. Abul Kashem, Xiao Zhou, Takao Nishizeki   +2 more
openalex   +3 more sources

Memory Requirements for Table Computations in Partial \sl k -Tree Algorithms

Algorithmica, 2000
This paper addresses memory requirement issues arising in implementations of algorithms on graphs of bounded treewidth. Such dynamic programming algorithms require a large data table for each vertex of a tree-decomposition T of the input graph. We give a linear-time algorithm that finds the traversal order of T minimizing the number of tables stored ...
Bengt Aspvall, Jan Arne Telle, Andrzej Proskurowski   +2 more
openalex   +4 more sources

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

Journal of Algorithms, 1990
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
Hans L. Bodlaender
openalex   +4 more sources

Practical algorithms on partial k-trees with an application to domination-like problems [PDF]

, 1993
Many NP-hard problems on graphs have polynomial, in fact usually linear, dynamic programming algorithms when restricted to partial k-trees (graphs of treewidth bounded by k), for fixed values of k. We investigate the practicality of such algorithms, both in terms of their complexity and their derivation, and account for the dependency on the treewidth ...
Jan Arne Telle, Andrzej Proskurowski
openalex   +2 more sources

Finding Independent Spanning Trees in Partial k-Trees

, 2000
Spanning trees rooted at a vertex r of a graph G are independent if, for each vertex v in G, all the paths connecting v and r in the trees are pairwise internally disjoint. In this paper we give a linear-time algorithm to find the maximum number of independent spanning trees rooted at any given vertex r in partial k-trees G, that is, graphs G with tree-
Xiao Zhou, Takao Nishizeki
openalex   +3 more sources

An NC parallel algorithm for generalized vertex-rankings of partial k-trees

Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN'97), 2002
A c-vertex-ranking of a graph G for a positive integer c is a labeling of the vertices of G with integers such that, for any label i, deletion of all vertices with labels >i leaves connected components, each having at most c vertices with label i. We present a parallel algorithm to find a c-vertex-ranking of a partial k-tree using the minimum number of
M.A. Kashem, Xiao Zhou, Takao Nishizeki
openalex   +2 more sources

Sequential and parallel algorithms for embedding problems on classes of partial k-trees

, 1994
We present sequential and parallel algorithms for various embedding problems on bounded degree partial k-trees and k-connected partial k-trees; these include subgraph isomorphism and topological embedding, known to be NP-complete for general partial k-trees.
Arvind Gupta, Naomi Nishimura
openalex   +3 more sources

Seeing Arboretum for the (partial k-) Trees [PDF]

, 2020
The idea of applying a dynamic programming strategy to evaluating certain objective functions on trees is fairly straightforward. The road for this idea to develop into theories of width parameters has been not so straight. Hans Bodlaender has played a major role in the process of mapping out that road.
Andrzej Proskurowski, Stefan Arnborg
openaire   +1 more source

Some of the next articles are maybe not open access.

Related searches:

Parametric module allocation on partial k-trees

IEEE Transactions on Computers, 1993
The problem of allocating modules to processors in a distributed system to minimize total costs when the underlying communication graph is a partial k-tree and all costs are linear functions of a real parameter t is considered. It is shown that if the number of processors is fixed, the sequence of optimum assignments that are obtained as t varies from ...
D. Fernandez-Baca, A. Medepalli
openaire   +2 more sources