Results 151 to 160 of about 855,011 (194)

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.
Xiao Zhou, Shunsuke Tamura, Takao Nishizeki   +2 more
openalex   +2 more sources

Counting H-colorings of partial k-trees

Theoretical Computer Science, 2002
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Josep Dı́az, Marı́a Serna, Dimitrios M. Thilikos   +2 more
openalex   +2 more sources

Finding Edge-disjoint Paths in Partial k-Trees

, 1996
For a given graph G and p pairs (si, ti), 1≤i≤p, of vertices in G, the edge-disjoint paths problem is to find p pairwise edge-disjoint paths Pi, 1≤i≤p, connecting si and ti. Many combinatorial problems can be efficiently solved for partial k-trees (graphs of treewidth bounded by a fixed integer k), but it has not been known whether the edge-disjoint ...
朱麗 田村, 隆夫 西関
  +4 more sources

Regular-factors in the complements of partial k-trees

, 1995
We consider the problem of recognizing graphs containing an f-factor (for any constant f) over the class of partial k-tree complements. We also consider a variation of this problem that only recognizes graphs containing a connected f-factor: this variation generalizes the Hamiltonian circuit problem. We show that these problems have O(n) algorithms for
Damon Kaller, Arvind Gupta, Tom Shermer
openalex   +2 more sources

Algorithms for Vertex Partitioning Problems on Partial k-Trees

SIAM Journal on Discrete Mathematics, 1997
Summary: We consider a large class of vertex partitioning problems and apply to them the theory of algorithm design for problems restricted to partial \(k\)-trees. We carefully describe the details of algorithms and analyze their complexity in an attempt to make the algorithms feasible as solutions for practical applications.
Jan Arne Telle, Andrzej Proskurowski
openalex   +2 more sources

Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees [PDF]

Journal of Algorithms, 2002
In this paper, graph coloring problems are studied, where each vertex receives a set of specified size of colors. These sets can be contiguous, in which case the problem models nonpreemtive scheduling, or arbitrary, which models preemtive scheduling. Given a graph with specified for each vertex the number of colors one has to give it, the paper studies
Magnús M. Halldórsson, Guy Kortsarz
openalex   +3 more sources

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 ...
David Fernández‐Baca, Anand Medepalli
openalex   +2 more sources

A Linear Algorithm for Finding Total Colorings of Partial k-Trees

, 1999
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. The total coloring problem is to find a total coloring of a given graph with the minimum number of colors. Many combinatorial problems can be efficiently solved for partial k-trees, i.
Shuji Isobe, Xiao Zhou, Takao Nishizeki
openalex   +3 more sources

A linear algorithm for edge-coloring partial k-trees

, 1993
Many combinatorial problems can be efficiently solved for partial k-trees. The edge-coloring problem is one of a few combinatorial problems for which no linear-time algorithm has been obtained for partial k-trees. The best known algorithm solves the problem for partial k-trees G in time \(O\left( {n\Delta ^{2^{2\left( {k + 1} \right)} } } \right ...
Xiao Zhou, Shin-ichi Nakano, Takao Nishizeki   +2 more
openalex   +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
openalex   +2 more sources