Characterization of partial 3-trees in terms of three structures
A graph \(G=(V,E)\) (simple and undirected) is a k-tree if there exists a bijection \(A:\{1,2,...,n\}\to V\) \((| V| =n>k)\) such that \(\Lambda (A(p))=\Gamma (A(p))-\{A(1),...,A(p)\}\) forms a clique and \(| \Lambda (A(p))| =k\) for all \(p=1,...,n-k\). A graph \(G=(V,E)\) is called a partial k-tree if it can be extended by adding some edges into a k-tree \(H=(V,F)\), \(F\supset E\). The paper contains several assertions concerning characterization of partial k-trees for both general k and \(k=3\). Eventually, an algorithm with a polynomial \((O(n^ 2))\) time convexity is presented enabling to recognize 3-trees.
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 3420184 (Why is no real title available?)
- Networks immune to isolated failures
- On simple characterizations of k-trees
- Properties and characterizations of k ‐trees
- Separating subgraphs in k-trees: Cables and caterpillars
- Steiner trees, partial 2–trees, and minimum IFI networks
- The nonexistence of reduction rules giving an embedding into a \(k\)-tree
- Algorithms and obstructions for linear-width and related search parameters
- Reduction algorithms for graphs of small treewidth
- Recognizing \(P_ 3\)-structure: A switching approach
- PERTURBED INVARIANT UNDER A CYCLIC PERMUTATION WITH TRACE OF NEUTRINO MASS MATRIX REMAIN CONSTANT
- NC Algorithms for Recognizing Partial 2-Trees and 3-Trees
- A characterization of partial 3-trees
- Characterization and Recognition of Partial 3-Trees
- scientific article; zbMATH DE number 4008410 (Why is no real title available?)
- Graph decompositions and tree automata in reasoning with uncertainty
- Constructive linear time algorithms for branchwidth
- Minimum size tree-decompositions
- The three-in-a-tree problem
- Forbidden minors characterization of partial 3-trees
This page was built for publication: Characterization of partial 3-trees in terms of three structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1086577)
