scientific article; zbMATH DE number 3974289

MaRDI QIDQ3740231zbMATH OpenFDO

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

Publication date 1985

zbMATH Keywords

treedomination numberNP-complete problemsrecursive graphtheory of linear computation

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4049086
• Linear-time computation of optimal subgraphs of decomposable graphs
• scientific article; zbMATH DE number 4024784
• scientific article; zbMATH DE number 1302196
• Linear algorithm for domatic number problem on interval graphs

Cited in

(31)

• Practical algorithms for MSO model-checking on tree-decomposable graphs
• Matchability and \(k\)-maximal matchings
• On the graph traversal method for evaluating linear binary-chain programs
• A linear algorithm for restructuring a graph
• Global defensive alliances of trees and Cartesian product of paths and cycles
• Generalized domination and efficient domination in graphs
• Bibliography on domination in graphs and some basic definitions of domination parameters
• Algorithms for recognition of regular properties and decomposition of recursive graph families
• Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results
• A recurrence template for several parameters in series-parallel graphs
• Generalized subgraph-restricted matchings in graphs
• Graph decompositions and tree automata in reasoning with uncertainty
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On the problem of domino recognition
• scientific article; zbMATH DE number 5811672 (Why is no real title available?)
• Universal minimal total dominating functions of trees
• Linear-time computation of optimal subgraphs of decomposable graphs
• Treewidth computations. I: Upper bounds
• Maximal irredundant functions
• Systematic generation of linear graphs - check and extension of the list of Uhlenbeck and Ford
• Nearly perfect sets in graphs
• The \(k\)-path coloring problem in graphs of bounded treewidth: an application in integrated circuit manufacturing
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• ILIGRA: an efficient inverse line graph algorithm
• Gainfree Leontief substitution flow problems
• Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
• The monadic second-order logic of graphs : Definable sets of finite graphs
• Regularity and locality in \(k\)-terminal graphs
• A linear‐time algorithm for broadcast domination in a tree
• Fixed-parameter tractability of treewidth and pathwidth
• A simple linear-time algorithm for finding path-decompositions of small width

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3740231)