Results 231 to 240 of about 102,821 (271)
Vertex partitioning problems on partial k-trees
, 1996 We 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
Arvind Gupta +3 more
openalex +3 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
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 +2 more
openalex +2 more sources
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
Linear-Time Algorithms for Partial \boldmath k -Tree Complements
Algorithmica, 2000 It 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,
Arvind Gupta +2 more
openalex +2 more sources
Marking Games and the Oriented Game Chromatic Number of Partial k -Trees
Graphs and Combinatorics, 2003 The oriented graph coloring game was introduced by \textit{J. Nešetřil} and \textit{E. Sopena} [Electron. J. Comb. 8, Research Paper R14 (2001; Zbl 0982.05049)] as follows: Given an oriented graph \(G=(V,A)\) and a tournament \(T = (C,D)\), two players alternately color vertices of \(G\) with colors from the set \(C\) such that, if \(v \in V\) is to be
Zs. Tuza, H. A. Kierstead
openalex +3 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
On some optimization problems on k-trees and partial k-trees
Location Science, 1996 openalex +2 more sources