Results 1 to 10 of about 367 (238)
Completely Independent Spanning Trees in (Partial) k-Trees
Discussiones Mathematicae Graph Theory, 2015 Two spanning trees T1 and T2 of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T1 and T2 are internally disjoint.
Matsushita Masayoshi +2 more
doaj +4 more sources
Transversals of Longest Cycles in Partial $k$-Trees and Chordal Graphs [PDF]
Journal of Graph Theory, 2019 AbstractLet be the minimum cardinality of a set of vertices that intersects every longest cycle of a 2‐connected graph . We show that if is a partial ‐tree and that if is chordal, where is the cardinality of a maximum clique in . Those results imply that all longest cycles intersect in 2‐connected series‐parallel graphs and in 3‐trees.
Juan Gutiérrez
openalex +5 more sources
Algorithms for generalized vertex-rankings of partial k-trees
Theoretical Computer Science, 2000 AbstractA c-vertex-ranking of a graph G for a positive integer c is a labeling of the vertices of G with integers such that, for any label i, deletion of all vertices with labels >i leaves connected components, each having at most c vertices with label i. A c-vertex-ranking is optimal if the number of labels used is as small as possible.
Md. Abul Kashem +2 more
openalex +2 more sources
The complexity of subgraph isomorphism for classes of partial k-trees
Theoretical Computer Science, 1996 AbstractWe present a clear demarcation between classes of bounded tree-width graphs for which the subgraph isomorphism problem is NP-complete and those for which it can be solved in polynomial time. In previous work, it has been shown that this problem is solvable in polynomial time if the source graph either has bounded degree or is k-connected, for k
Arvind Gupta, Naomi Nishimura
openalex +3 more sources
On some optimization problems on k-trees and partial k-trees
Discrete Applied Mathematics, 1994 AbstractA k-tree is a graph that can be reduced to the k-complete graph by sequentially removing k-degree vertices with completely connected neighbors. Partial k-trees are graphs embeddable in a k-tree with the same vertex set. In this paper we develop efficient algorithms for several path distance optimization problems on partial k-trees, and k-cable ...
Daniel Granot, Darko Skorin‐Kapov
openalex +3 more sources
Efficient sets in partial k-trees
Discrete Applied Mathematics, 1993 AbstractWe generalize the result of Bernhard, Hedetniemi and Jacobs by providing a linear time algorithm that computes the efficiency of a partial k-tree that is given with its embedding in a k-tree.
Jan Arne Telle, Andrzej Proskurowski
openalex +3 more sources
The inverse inertia problem for the complements of partial k -trees
Linear Algebra and its Applications, 2013 10 ...
Hein van der Holst
openalex +4 more sources
Counting H-Colorings of Partial k-Trees [PDF]
Theoretical Computer Science, 2001 AbstractThe problem of counting all H-colorings of a graph G with n vertices is considered. While the problem is, in general, #P-complete, we give linear time algorithms that solve the main variants of this problem when the input graph G is a k-tree or, in the case where G is directed, when the underlying graph of G is a k-tree.
Josep Dı́az +2 more
openalex +3 more sources
On the complexity of finding iso- and other morphisms for partial k-trees
Discrete Mathematics, 1992 AbstractThe problems to decide whether H⩽G for input graphs H, G where ⩽ is ‘isomorphic to a subgraph’, ‘isomorphic to an induced subgraphs’, ‘isomorphic to a subdivision’, ‘isomorphic to a contraction’ or their combination, are NP-complete. We discuss the complexity of these problems when G is restricted to be a partial k-tree (in other terminology ...
Jiřı́ Matoušek, Robin Thomas
openalex +3 more sources
Maximum packing for k-connected partial k-trees in polynomial time
Theoretical Computer Science, 2000 AbstractThe problem of determining the maximum number of node-disjoint subgraphs of a partial k-tree H on nH nodes that are isomorphic to a k-connected partial k-tree G on nG nodes is shown to be solvable in time O(nGk+1nH+nHk).
Anders Dessmark +2 more
openalex +3 more sources