Results 171 to 180 of about 855,011 (194)
Some of the next articles are maybe not open access.
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 +2 more
openaire +2 more sources
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 +2 more
openaire +2 more sources
Finding Independent Spanning Trees in Partial k-Trees
2000Spanning 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, 2009An 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 +2 more
openaire +1 more source
Marking Games and the Oriented Game Chromatic Number of Partial k -Trees
Graphs and Combinatorics, 2003The 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
Kierstead, H. A., Tuza, Zs.
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.
Xiao Zhou +2 more
openaire +1 more source
Definability Equals Recognizability of Partial 3-Trees and \sl k -Connected Partial \sl k -Trees
Algorithmica, 2000zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire +1 more source
The Edge-Disjoint Paths Problem is NP-Complete for Partial k-Trees
1998Many combinatorial problems are NP-complete for general graphs, but are not NP-complete for partial k-trees (graphs of treewidth bounded by a constant k) and can be efficiently solved in polynomial time or mostly in linear time for partial k-trees.
Xiao Zhou, Takao Nishizeki
openaire +1 more source
Practical algorithms on partial k-trees with an application to domination-like problems
, 1993 Jan Arne Telle, Andrzej Proskurowski
openalex +1 more source
A Linear Algorithm for Finding \boldmath[{ g,f }]-Colorings of Partial \boldmath{ k }-Trees
, 2000 K. Fuse, Xiao Zhou, T. Nishizeki
openalex +1 more source
On some optimization problems on k-trees and partial k-trees
Location Science, 1996openaire +1 more source