We prove that maximum H-matching (the problem of determining the maximum number of node-disjoint copies of the fixed graph H contained in a variable graph) is a Max SNP-hard problem for any graph H that has three or m...
详细信息
We prove that maximum H-matching (the problem of determining the maximum number of node-disjoint copies of the fixed graph H contained in a variable graph) is a Max SNP-hard problem for any graph H that has three or more nodes in some connected component. If H is connected and the degrees of the nodes in H are bounded by a constant the problem is Max SNP-complete.
作者：
LANSNER, ALILJENSTROM, HSANS
Studies of Artificial Neural Systems Department of Numerical Analysis and Computing Science Royal Institute of Technology S-100 44 Stockholm Sweden
The recent developments in computer capacity and algorithms, together with a tremendous growth of data in neuroscience have dramatically improved the possibilities of modeling and simulating certain brain structures a...
The recent developments in computer capacity and algorithms, together with a tremendous growth of data in neuroscience have dramatically improved the possibilities of modeling and simulating certain brain structures and activities with a considerable degree of realism. Although there is still a long way to go, some claim that we will one day be able to create artificial ''brains'' with similar capacity to the human brain, perhaps even surpassing it. Here we focus on these perspectives, discussing the potentials and limitations of today's computer models, and how far they might be able to take us.
Computer simulation of neuronal networks is rapidly becoming accepted as a powerful tool in neuroscience. We illustrate the trends in this field by looking at motor generation and control, with examples from recent mo...
详细信息
An intertwine of two graphs H and H′ is a graph G such that G contains both H and H′ as minors, but no proper minor of G contains both H and H′ as minors. We give an upper bound on the size of an intertwine of two ...
详细信息
We consider the combinatorial problem MAXFLS which consists, given a system of linear relations, of finding a maximum feasible subsystem, that is a solution satisfying as many relations as possible. The approximabilit...
详细信息
We study the role of complex neurodynamics in learning and associative memory using a neural network model of the olfactory cortex. By varying the noise level and a control parameter, corresponding to the level of neu...
详细信息
We study the role of complex neurodynamics in learning and associative memory using a neural network model of the olfactory cortex. By varying the noise level and a control parameter, corresponding to the level of neuromodulator or arousal, we analyze the resulting nonlinear dynamics during learning and recall of constant and oscillatory input. Point attractor, limit cycle, and strange attractor dynamics occur at different values of the control parameter. We show that oscillations and chaos-like behavior can give shorter recall times and more robust memory states than in static cases. In particular, we show that the recall time can reach a minimum for additive and multiplicative noise. Also noise-induced state transitions and noise-induced chaos-like behavior is demonstrated.< >
A query-reply system based on a Bayesian neural network is described. Strategies for generating questions which make the system both efficient and highly fault tolerant are presented. This involves having one phase of...
A query-reply system based on a Bayesian neural network is described. Strategies for generating questions which make the system both efficient and highly fault tolerant are presented. This involves having one phase of question generation intended to quickly reach a hypothesis followed by a phase where verification of the hypothesis is attempted. In addition, both phases have strategies for detecting and removing inconsistencies in the replies from the user. Also described is an explanatory mechanism which gives information related to why a certain hypotheses is reached or question asked. Specific examples of the systems behavior as well as the results of a statistical evaluation are presented.
This article shows how discrete derivative approximations can be defined so thatscale-space properties hold exactly also in the discrete domain. Starting from a set of natural requirements on the first processing stag...
详细信息
This article shows how discrete derivative approximations can be defined so thatscale-space properties hold exactly also in the discrete domain. Starting from a set of natural requirements on the first processing stages of a visual system,the visual front end, it gives an axiomatic derivation of how a multiscale representation of derivative approximations can be constructed from a discrete signal, so that it possesses analgebraic structure similar to that possessed by the derivatives of the traditional scale-space representation in the continuous domain. A family of kernels is derived that constitutediscrete analogues to the continuous Gaussian derivatives. The representation has theoretical advantages over other discretizations of the scale-space theory in the sense that operators that commute before discretizationcommute after discretization. Some computational implications of this are that derivative approximations can be computeddirectly from smoothed data and that this will giveexactly the same result as convolution with the corresponding derivative approximation kernel. Moreover, a number ofnormalization conditions are automatically satisfied. The proposed methodology leads to a scheme of computations of multiscale low-level feature extraction that is conceptually very simple and consists of four basic steps: (i)large support convolution smoothing, (ii)small support difference computations, (iii)point operations for computing differential geometric entities, and (iv)nearest-neighbour operations for feature detection. Applications demonstrate how the proposed scheme can be used for edge detection and junction detection based on derivatives up to order three.
This article presents: (i) a multiscale representation of grey-level shape called the scale-space primal sketch, which makes explicit both features in scale-space and the relations between structures at different scal...
详细信息
This article presents: (i) a multiscale representation of grey-level shape called the scale-space primal sketch, which makes explicit both features in scale-space and the relations between structures at different scales, (ii) a methodology for extracting significant blob-like image structures from this representation, and (iii) applications to edge detection, histogram analysis, and junction classification demonstrating how the proposed method can be used for guiding later-stage visual processes. The representation gives a qualitative description of image structure, which allows for detection of stable scales and associated regions of interest in a solely bottom-up data-driven way. In other words, it generates coarse segmentation cues, and can hence be seen as preceding further processing, which can then be properly tuned. It is argued that once such information is available, many other processing tasks can become much simpler. Experiments on real imagery demonstrate that the proposed theory gives intuitive results.
暂无评论