Results 241 to 250 of about 102,821 (271)

Finding Edge-Disjoint Paths in Partial k -Trees

Algorithmica, 2000
For a given graph \(G\) and \(p\) pairs \((s_i,t_i)\), \(1\leq i\leq p\), of vertices of \(G\), the edge-disjoint paths problem is to find \(p\) pairwise edge-disjoint paths \(P_i\), \(1\leq i \leq p\), connecting \(s_i\) and \(t_i\). This paper gives two algorithms for the edge-disjoint paths problem on partial \(k\)-trees.
Zhou, X., Tamura, S., Nishizeki, T.
openaire   +1 more source

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   +1 more source

Seeing Arboretum for the (partial k-) Trees

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.
Stefan Arnborg, Andrzej Proskurowski
openaire   +1 more source

Multicoloring Planar Graphs and Partial k-Trees

1999
We study the multicoloring problem with two objective functions: minimizing the makespan and minimizing the multisum. We focus on partial k-trees and planar graphs. In particular, we give polynomial time approximation schemes (PTAS) for both classes, for both preemptive and non-preemptive multisum colorings.
Magnús M. Halldórsson, Guy Kortsarz
openaire   +1 more source

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 ...
Arvind Gupta, Damon Kaller, Thomas Shermer   +2 more
openaire   +1 more source

Edge-Coloring Partialk-Trees

Journal of Algorithms, 1996
Summary: Many combinatorial problems can be efficiently solved for partial \(k\)-trees (graphs of treewidth bounded by \(k\)). The edge-coloring problem is one of the well-known combinatorial problems for which no efficient algorithms were previously known, except a polynomial-time algorithm of very high complexity.
Zhou, Xiao, Nakano, Shin-ichi, Nishizeki, Takao   +2 more
openaire   +2 more sources

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
openaire   +1 more source

A Polynomial-Time Algorithm for Finding Total Colorings of Partial k-Trees

International Journal of Foundations of Computer Science, 1998
A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Many combinatorial problems can be efficiently solved for partial k-trees, that is, graphs of treewidth bounded by a constant k.
Isobe, Shuji, Zhou, Xiao, Nishizeki, Takao   +2 more
openaire   +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
openaire   +1 more source

On the Structure of Contractible Edges in k-connected Partial k-trees

Graphs and Combinatorics, 2009
An edge in a graph is contractible if its contraction does not decrease the connectivity. In the paper the authors present results on the structure of contractible edges in \(k\)-trees and \(k\)-connected partial \(k\)-trees. They also construct a class of contraction critical \(2k\)-connected partial \(2k\)-trees.
Narayanaswamy, NS, Sadagopan, N, Chandran, Sunil L   +2 more
openaire   +1 more source