scientific article; zbMATH DE number 3974289
[For the entire collection see Zbl 0583.00003.] The paper is an introduction to the new theory of linear computation which not only explains the linearity of many of the known algorithms, but also predicts the existence of other linear algorithms. The theory is illustrated by applying it to the design of a variant of an existing linear algorithm for calculating the domination number of a tree. Also, the authors present tables indicating 20 families of graphs and 34 NP- complete problems for which this theory predicts that a linear algorithm can be constructed for solving the given problem for any graph in the given family.
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Generalized domination and efficient domination in 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 recurrence template for several parameters in series-parallel graphs
- Regularity and locality in \(k\)-terminal graphs
- A linear algorithm for restructuring a graph
- Generalized subgraph-restricted matchings in graphs
- Gainfree Leontief substitution flow problems
- Nearly perfect sets in graphs
- Universal minimal total dominating functions of trees
- Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
- Maximal irredundant functions
- The \(k\)-path coloring problem in graphs of bounded treewidth: an application in integrated circuit manufacturing
- Fixed-parameter tractability of treewidth and pathwidth
- scientific article; zbMATH DE number 5811672 (Why is no real title available?)
- On the problem of domino recognition
- Global defensive alliances of trees and Cartesian product of paths and cycles
- Graph decompositions and tree automata in reasoning with uncertainty
- Linear-time computation of optimal subgraphs of decomposable graphs
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results
- A linear‐time algorithm for broadcast domination in a tree
- On the graph traversal method for evaluating linear binary-chain programs
- Matchability and \(k\)-maximal matchings
- The monadic second-order logic of graphs : Definable sets of finite graphs
- A simple linear-time algorithm for finding path-decompositions of small width
- Systematic generation of linear graphs - check and extension of the list of Uhlenbeck and Ford
- Bibliography on domination in graphs and some basic definitions of domination parameters
- ILIGRA: an efficient inverse line graph algorithm
- Treewidth computations. I: Upper bounds
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)