Characterization and Recognition of Partial 3-Trees

DOI10.1137/0607033zbMath0597.05027OpenAlexW2038674294MaRDI QIDQ3728922

Andrzej Proskurowski, Stefan Arnborg

Publication date: 1986

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0607033

zbMATH Keywords

polynomial time algorithm graph reduction k-tree 3-trees reliability of communication networks complexity of queries in data base systems confluent reduction recognizing subgraphs

Mathematics Subject Classification ID

Trees (05C05) Reliability, availability, maintenance, inspection in operations research (90B25) Planar graphs; geometric and topological aspects of graph theory (05C10) Information storage and retrieval of data (68P20)

Related Items (51)

Safe separators for treewidth ⋮ Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ Seeing Arboretum for the (partial k-) Trees ⋮ Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems ⋮ Improved self-reduction algorithms for graphs with bounded treewidth ⋮ The nonexistence of reduction rules giving an embedding into a \(k\)-tree ⋮ Regularity and locality in \(k\)-terminal graphs ⋮ Steiner problem in Halin networks ⋮ Canonical representations of partial 2-and 3-trees ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Practical algorithms on partial k-trees with an application to domination-like problems ⋮ Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs ⋮ An improved planar graph product structure theorem ⋮ A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata ⋮ Graph decompositions and tree automata in reasoning with uncertainty ⋮ Linear time algorithms for NP-hard problems restricted to partial k- trees ⋮ Constructive linear time algorithms for branchwidth ⋮ The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues ⋮ The tree-width of C ⋮ Complexity of Finding Embeddings in a k-Tree ⋮ Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth ⋮ Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results ⋮ Unnamed Item ⋮ Forbidden minors characterization of partial 3-trees ⋮ On two dual classes of planar graphs ⋮ Tree-width, clique-minors, and eigenvalues. ⋮ Minimum size tree-decompositions ⋮ Characterizing graphs of small carving-width ⋮ Characterization and complexity of uniformly nonprimitive labeled 2-structures ⋮ Minimum size tree-decompositions ⋮ Canonical representations of partial 2- and 3-trees ⋮ Monadic second-order evaluations on tree-decomposable graphs ⋮ Efficient sets in partial \(k\)-trees ⋮ Tree decomposition and discrete optimization problems: a survey ⋮ An O\((nm)\) algorithm for a special case of the multimedian location problem on a tree ⋮ Complexity of path-forming games ⋮ Treewidth computations. II. Lower bounds ⋮ A sufficiently fast algorithm for finding close to optimal clique trees ⋮ Efficient frequent connected subgraph mining in graphs of bounded tree-width ⋮ Using a hybrid of exact and genetic algorithms to design survivable networks ⋮ Recognizing hyperelliptic graphs in polynomial time ⋮ Characterizations of H-graphs ⋮ On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs ⋮ Heuristic and metaheuristic methods for computing graph treewidth ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Computational properties of argument systems satisfying graph-theoretic constraints ⋮ A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata ⋮ Surfaces, tree-width, clique-minors, and partitions ⋮ Generating internally four-connected graphs ⋮ Reduction algorithms for graphs of small treewidth ⋮ On some optimization problems on \(k\)-trees and partial \(k\)-trees

Cites Work

This page was built for publication: Characterization and Recognition of Partial 3-Trees