Results 191 to 200 of about 367 (238)
Some of the next articles are maybe not open access.
On the Complements of Partial k-Trees
1999We 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 +2 more
openaire +2 more sources
Algorithms for Vertex Partitioning Problems on Partial k-Trees
SIAM Journal on Discrete Mathematics, 1997In this paper, 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.
Andrzej Proskurowski, Jan Arne Telle
openaire +2 more sources
Regular-factors in the complements of partial k-trees
1995We 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
Arvind Gupta +2 more
openaire +2 more sources
Multicoloring Planar Graphs and Partial k-Trees
1999We 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 +2 more sources
On some problems on k-trees and partial k-trees
1989The objective of this thesis is to investigate some structural and algorithmic properties of k-trees and partial k-trees. A k-tree can be constructed from a k-complete graph by recursively adding a new vertex which is adjacent to all vertices of an existing k-complete subgraph. Partial k-trees are graphs embeddable in a k-tree with the same vertex set.
openaire +2 more sources
A Polynomial-Time Algorithm for Finding Total Colorings of Partial k-Trees
International Journal of Foundations of Computer Science, 1998A 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.
Takao Nishizeki, Xiao Zhou, Shuji Isobe
openaire +3 more sources
On the Structure of Contractible Edges in k-connected Partial k-trees
Graphs and Combinatorics, 2009Contraction of an edge e merges its end points into a new single vertex, and each neighbor of one of the end points of e is a neighbor of the new vertex. An edge in a k-connected graph is contractible if its contraction does not result in a graph with lesser connectivity; otherwise the edge is called non-contractible.
Narayanaswamy, NS +2 more
openaire +2 more sources
A parallel algorithm for edge-coloring partial k-trees
1994Many 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 NC algorithms have been obtained for partial k-trees.
Takao Nishizeki +2 more
openaire +2 more sources
A Linear Algorithm for Finding Total Colorings of Partial k-Trees [PDF]
, 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.
Takao Nishizeki, Xiao Zhou, Shuji Isobe
openaire +1 more source
Optimal broadcasting in almost trees and partial k-trees
1998We consider message broadcasting in networks that have almost tree topology. The source node of the input network has a single message which has to be broadcasted to all nodes of the network. In every time unit each node that has already received the message can send it to one of its neighbors.
Anders Dessmark +3 more
openaire +2 more sources