𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Note on complexity of computing the domination of binary systems

✍ Scribed by A.A. Chernyak; Zh.A. Chernyak

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
419 KB
Volume
73
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

The problem of computing the domination of a coherent binary system all minimal paths sets of which have equal cardinality k (k > l), is proved to be #P-complete. Some corollaries are given.

πŸ“œ SIMILAR VOLUMES

On the computational complexity of upper
On the computational complexity of upper total domination
✍ Qizhi Fang πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 359 KB

Let G = (V; E) be an undirected graph. Upper total domination number t (G) is the maximum cardinality over all minimal total dominating sets of G, and upper fractional total domination number t (G) is the maximum weight over all minimal total dominating functions of G. In this paper we show that: (1

A note on the characterization of domina
A note on the characterization of domination perfect graphs
✍ Jason Fulman πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 191 KB

## Abstract A graph __G__ is domination perfect if for each induced subgraph __H__ of __G__, Ξ³(__H__) = __i__(__H__), where Ξ³ and __i__ are a graph's domination number and independent domination number, respectively. Zverovich and Zverovich [3] offered a finite forbidden induced characterization of

A note on the computation of Markovian s
A note on the computation of Markovian systems
✍ N. Limnios πŸ“‚ Article πŸ“… 1988 πŸ› Elsevier Science 🌐 English βš– 180 KB

In this paper we propose a new method for the numerical resolution of the Kolmogorov equations for continuous time Markov chains. The numerical treatment required is very simple as for the discrete time Markov chain. An accurate error analysis is derived by Shur's theorem.