scientific article

zbMath0603.68040MaRDI QIDQ3740231

Stephen T. Hedetniemi, T. V. Wimer, Renu C. Laskar

Publication date: 1985

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

treeNP-complete problemsdomination numberrecursive graphtheory of linear computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items (25)

A recurrence template for several parameters in series-parallel graphs ⋮ Regularity and locality in \(k\)-terminal graphs ⋮ Universal minimal total dominating functions of trees ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs ⋮ Graph decompositions and tree automata in reasoning with uncertainty ⋮ Linear time algorithms for NP-hard problems restricted to partial k- trees ⋮ The \(k\)-path coloring problem in graphs of bounded treewidth: an application in integrated circuit manufacturing ⋮ Generalized domination and efficient domination in graphs ⋮ Maximal irredundant functions ⋮ Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results ⋮ Matchability and \(k\)-maximal matchings ⋮ Global defensive alliances of trees and Cartesian product of paths and cycles ⋮ The monadic second-order logic of graphs : Definable sets of finite graphs ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Algorithms for recognition of regular properties and decomposition of recursive graph families ⋮ Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families ⋮ A simple linear-time algorithm for finding path-decompositions of small width ⋮ Treewidth computations. I: Upper bounds ⋮ Generalized subgraph-restricted matchings in graphs ⋮ A linear‐time algorithm for broadcast domination in a tree ⋮ Gainfree Leontief substitution flow problems ⋮ Nearly perfect sets in graphs ⋮ Myhill-Nerode Methods for Hypergraphs ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters

This page was built for publication: