Results 161 to 170 of about 855,011 (194)
Memory Requirements for Table Computations in Partial \sl k -Tree Algorithms
Algorithmica, 2000 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Bengt Aspvall +2 more
openalex +2 more sources
Optimal broadcasting in almost trees and partial k-trees
, 1998 We 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
openalex +2 more sources
The complexity of subgraph isomorphism for classes of partial k-trees
Theoretical Computer Science, 1996 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Arvind Gupta, Naomi Nishimura
openalex +3 more sources
Linear time algorithms for NP-hard problems restricted to partial k-trees
Discrete Applied Mathematics, 1989 We present and illustrate by a sequence of examples an algorithm paradigm for solving NP-hard problems on graphs resticted to partial graphs of k- trees and given with an embedding in a k-tree. Such algorithms, linear in the size of the graph but exponential or superexponential in k, exist for most NP-hard problems that have linear time algorithms for ...
Stefan Arnborg, Andrzej Proskurowski
openalex +3 more sources
Some of the next articles are maybe not open access.
Related searches:
Related searches:
Vertex partitioning problems on partial k-trees
1996We describe a general approach to obtain polynomial-time algorithms over partial k-trees for graph problems in which the vertex set is to be partitioned in some way. We encode these problems with formulae of the Extended Monadic Second-order (or EMS) logic. Such a formula can be translated into a polynomial-time algorithm automatically. We focus on the
Gupta, A. +3 more
openaire +2 more sources
Seeing Arboretum for the (partial k-) Trees
2020The 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
A POLYNOMIAL-TIME ALGORITHM FOR FINDING TOTAL COLORINGS OF PARTIAL k-TREES
International Journal of Foundations of Computer Science, 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. Many combinatorial problems can be efficiently solved for partial k-trees, that is, graphs of treewidth bounded by a constant k.
Shuji Isobe, Xiao Zhou, Takao Nishizeki
openalex +3 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 +1 more source
Linear-Time Algorithms for Partial \boldmath k -Tree Complements
Algorithmica, 2000It is known that a graph decision problem can be solved in linear time over partial k -trees if the problem can be defined in Monadic Second-order (or MS) logic. MS logic allows quantification of vertex and edge subsets, with respect to which logical sentences can encode many different conditions that an input graph must satisfy. It is not always clear,
A. Gupta, T. Shermer, D. Kaller
openaire +1 more source
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 ...
Arvind Gupta +2 more
openaire +1 more source