On simple characterizations of k-trees
From MaRDI portal
Publication:1844861
DOI10.1016/0012-365X(74)90042-9zbMath0285.05128OpenAlexW2081414924MaRDI QIDQ1844861
Publication date: 1974
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0012-365x(74)90042-9
Related Items (83)
Isomorphism Testing in Hookup Classes ⋮ Heuristics for the network design problem with connectivity requirements ⋮ Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ The nonexistence of reduction rules giving an embedding into a \(k\)-tree ⋮ \(k\)-NLC graphs and polynomial algorithms ⋮ Characterization of partial 3-trees in terms of three structures ⋮ The most reliable series-parallel networks ⋮ Sequential and parallel algorithms for embedding problems on classes of partial k-trees ⋮ Community Structure Inspired Algorithms for SAT and #SAT ⋮ On the structure of contractible edges in \(k\)-connected partial \(k\)-trees ⋮ Approximation algorithms for treewidth ⋮ Characterization and Recognition of Partial 3-Trees ⋮ Approximation of the Quadratic Knapsack Problem ⋮ Nested locally Hamiltonian graphs and the Oberly-Sumner conjecture ⋮ Some possible new directions for combinatorial matrix analysis ⋮ Unnamed Item ⋮ A characterization of partial 3-trees ⋮ Complexity of Finding Embeddings in a k-Tree ⋮ Maximum matching width: new characterizations and a fast algorithm for dominating set ⋮ Drawing Planar Graphs with Few Geometric Primitives ⋮ On \(\alpha\)-excellent graphs ⋮ The Clique-Width of Tree-Power and Leaf-Power Graphs ⋮ Sphere representations, stacked polytopes, and the Colin de Verdière number of a graph ⋮ On the structure and deficiency of \(k\)-trees with bounded degree ⋮ Shape Measures of Random Increasing k-trees ⋮ Isomorphism testing of k-trees is in NC, for fixed k ⋮ A PTAS for the Cluster Editing Problem on Planar Graphs ⋮ A note on the saturation number of the family of \(k\)-connected graphs ⋮ Parameters Tied to Treewidth ⋮ On the extension of a partial metric to a tree metric ⋮ On the complexity of the black-and-white coloring problem on some classes of perfect graphs ⋮ An efficient representation of chordal graphs ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Antimatroids and balanced pairs ⋮ A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs ⋮ One-phase algorithm for the determination of minimal vertex separators of chordal graphs ⋮ Line graphs of bounded clique-width ⋮ Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time ⋮ The complexity of subgraph isomorphism for classes of partial k-trees ⋮ New width parameters for SAT and \#SAT ⋮ Steiner trees, partial 2–trees, and minimum IFI networks ⋮ A technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-paths ⋮ Edge clique partition in \((k,\ell)\)-graphs ⋮ Chromatic index, treewidth and maximum degree ⋮ Canonical representations of partial 2- and 3-trees ⋮ A characterization of \(k\)-trees ⋮ Complexity of some graph-based bounds on the probability of a union of events ⋮ On the SPANNING \(k\)-TREE problem ⋮ Tree decomposition and discrete optimization problems: a survey ⋮ Monotonicity and expansion of global secure sets ⋮ A coding algorithm for Rényi trees ⋮ The specification of 2-trees ⋮ On the complexity of some subgraph problems ⋮ Bijective linear time coding and decoding for \(k\)-trees ⋮ Subclasses of \(k\)-trees: characterization and recognition ⋮ The triangles method to buildX-trees from incomplete distance matrices ⋮ A Separator Theorem for Chordal Graphs ⋮ Monadic Second Order Logic on Graphs with Local Cardinality Constraints ⋮ Vertex disjoint paths on clique-width bounded graphs ⋮ Using a hybrid of exact and genetic algorithms to design survivable networks ⋮ On \(k\)-tree containment graphs of paths in a tree ⋮ Extremal interval graphs ⋮ On the chordality of a graph ⋮ Two strikes against perfect phylogeny ⋮ Linear algorithms on recursive representations of trees ⋮ Edge-maximal graphs of branchwidth \(k\): The \(k\)-branches ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ A linear time algorithm for computing the most reliable source on a series--parallel graph with unreliable edges ⋮ The NLC-width and clique-width for powers of graphs of bounded tree-width ⋮ Networks immune to isolated failures ⋮ On zero-sum spanning trees and zero-sum connectivity ⋮ \(k\)-Wiener index of a \(k\)-plex ⋮ Improper sum-list colouring of 2-trees ⋮ Extremal graphs having no matching cuts ⋮ Requiring chords in cycles ⋮ A CHARACTERIZATION OF k-TH POWERS Pn,k OF PATHS IN TERMS OF k-TREES ⋮ Separating subgraphs in k-trees: Cables and caterpillars ⋮ Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey ⋮ A Cryptographic Code Based on Digraphs ⋮ The Reduced Prüfer Code for Rooted Labelled k-Trees ⋮ Edge-maximal graphs of branchwidth k ⋮ Unnamed Item ⋮ The square of a chordal graph
Cites Work
This page was built for publication: On simple characterizations of k-trees
