Results 211 to 220 of about 818,578 (247)

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

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

Definability Equals Recognizability of Partial 3-Trees and \sl k -Connected Partial \sl k -Trees

Algorithmica, 2000
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Damon Kaller
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

On the Complements of Partial k-Trees

1999
We introduce new techniques for studying the structure of partial k-trees. In particular, we show that the complements of partial k-trees provide an intuitively-appealing characterization of partial k-tree obstructions. We use this characterization to obtain a lower bound of 2Ω(k log k) on the number of obstructions, significantly improving the ...
Damon Kaller, Arvind Gupta, Thomas C. Shermer   +2 more
openaire   +2 more sources