Detecting Fixed Patterns in Chordal Graphs in Polynomial Time

The Contractibility problem takes as input two graphs G and H, and the task is to decide whether H can be obtained from G by a sequence of edge contractions. The Induced Minor and Induced Topological Minor problems are similar, but the first allows both edge contractions and vertex deletions, whereas the latter allows only vertex deletions and vertex dissolutions. All three problems are NP-complete, even for certain fixed graphs H. We show that these problems can be solved in polynomial time for every fixed H when the input graph G is chordal. Our results can be considered tight, since these problems are known to be W[1]-hard on chordal graphs when parameterized by the size of H. To solve Contractibility and Induced Minor, we define and use a generalization of the classic Disjoint Paths problem, where we require the vertices of each of the k paths to be chosen from a specified set. We prove that this variant is NP-complete even when k=2, but that it is polynomial-time solvable on chordal graphs for every fixed k. Our algorithm for Induced Topological Minor is based on another generalization of Disjoint Paths called Induced Disjoint Paths, where the vertices from different paths may no longer be adjacent. We show that this problem, which is known to be NP-complete when k=2, can be solved in polynomial time on chordal graphs even when k is part of the input. Our results fit into the general framework of graph containment problems, where the aim is to decide whether a graph can be modified into another graph by a sequence of specified graph operations. Allowing combinations of the four well-known operations edge deletion, edge contraction, vertex deletion, and vertex dissolution results in the following ten containment relations: (induced) minor, (induced) topological minor, (induced) subgraph, (induced) spanning subgraph, dissolution, and contraction. Our results, combined with existing results, settle the complexity of each of the ten corresponding containment problems on chordal graphs.     

A surrogate-based optimization method with RBF neural network enhanced by linear interpolation and hybrid infill strategy

In engineering, it is computationally prohibitive to directly employ costly models in optimization. Therefore, surrogate-based optimization is developed to replace the accurate models with cheap surrogates during optimization for efficiency. The two key issues of surrogate-based optimization are how to improve the surrogate accuracy by making the most of the available training samples, and how to sequentially augment the training set with certain infill strategy so as to gradually improve the surrogate accuracy and guarantee the convergence to the real global optimum of the accurate model. To address these two issues, a radial basis function neural network (RBFNN) based optimization method is proposed in this paper. First, a linear interpolation (LI) based RBFNN modelling method, LI-RBFNN, is developed, which can enhance the RBFNN accuracy by enforcing the gradient match between the surrogate and the trend observed from the training samples. Second, a hybrid infill strategy is proposed, which uses the surrogate prediction error based surrogate lower bound as the optimization objective to locate the promising region and meanwhile employs a linear interpolation-based sequential sampling approach to improve the surrogate accuracy globally. Finally, extensive tests are investigated and the effectiveness and efficiency of the proposed methods are demonstrated.     

Analysis of tubular structures in three-dimensional confocal images

Knowledge about the relationship between morphology and the function of neurons is an important instrument in understanding the role that neurons play in information processing in the brain. In paricular, the diameter and length of segments in dendritic arborization are considered to be crucial morphological features. Consequently, accurate detection of morphological features such as centre line position and diameter is a prerequisite to establish this relationship. Accurate detection of neuron morphology from confocal microscope images is hampered by the low signal to noise ratio of the images and the properties of the microscope point spread function (PSF). The size and the anisotropy of the PSF causes feature detection to be biased and orientation dependent. We deal with these problems by utilizing Gaussian image derivatives for feature detection. Gaussian kernels provide for image derivative estimates with low noise sensitivity. Features of interest such as centre line positions and diameter in a tubular neuronal segment of a dendritic tree can be detected by calculating and subsequently utilizing Gaussian image derivatives. For diameter measurement the microscope PSF is incorporated into the derivative calculation. Results on real and simulated confocal images reveal that centre line position and diameter can be estimated accurately and are bias free even under realistic imaging conditions.     

Evaluating meeting support tools

Many attempts are underway for developing meeting support tools, but less attention is paid to the evaluation of meetingware. This article describes the development and testing of an instrument for evaluating meeting tools. First, we specified the object of evaluation—meetings—by means of a set of input, process, and outcome factors. Then, we designed the process of evaluation, consisting of, first, the generation of meeting behavior in the form of a controlled series of meetings within the context of a project and, second, the measurement of the identified meeting factors. To measure these factors, a rating scale, questionnaires, and information flow analysis were used. Next, the instrument was tested, and the factors for successful meetings were determined in 13 projects in which four participants had to meet four times. The evaluation instrument proved to be a reliable and useful aid for the development and improvement of meeting tools.     

Koordination in Service Value Networks

The fundamental paradigm shift from traditional value chains to agile service value networks implies new economic and organizational challenges. As coordination mechanisms, auctions have proven to perform quite well in situations where intangible and heterogeneous goods are traded. Nevertheless, traditional approaches in the area of multidimensional combinatorial auctions are not quite suitable to enable the trade of composite services. A flawless service execution and therefore the requester’s valuation highly depends on the accurate sequence of the functional parts of the composition, meaning that in contrary to service bundles, composite services only generate value through a valid order of their components. The authors present an abstract model as a formalization of service value networks. The model comprehends a graph-based mechanism implementation to allocate multidimensional service offers within the network, to impose penalties for non-performance and to determine prices for complex services. The mechanism and the bidding language support various types of QoS attributes and their (semantic) aggregation. It is analytically shown that this variant is incentive compatible with respect to all dimensions of the service offer (quality and price). Based on these results, the authors numerically analyze strategic behavior of participating service providers regarding possible collusion strategies.     

4D MRI Flow Coupled to Physics‐Based Fluid Simulation for Blood‐Flow Visualization

Modern MRI measurements deliver volumetric and time‐varying blood‐flow data of unprecedented quality. Visual analysis of these data potentially leads to a better diagnosis and risk assessment of various cardiovascular diseases. Recent advances have improved the speed and quality of the imaging data considerably. Nevertheless, the data remains compromised by noise and a lack of spatiotemporal resolution. Besides imaging data, also numerical simulations are employed. These are based on mathematical models of specific features of physical reality. However, these models require realistic parameters and boundary conditions based on measurements. We propose to use data assimilation to bring measured data and physically‐based simulation together, and to harness the mutual benefits. The accuracy and noise robustness of the coupled approach is validated using an analytic flow field. Furthermore, we present a comparative visualization that conveys the differences between using conventional interpolation and our coupled approach.     

A software process for the construction of predictable on‐board embedded real‐time systems

The rise of the ‘cheaper, faster, better’ mission paradigm increasingly challenges the industrial development of satellite systems. The novel paradigm will have a profound impact on the production of the real‐time software embedded on board new‐generation systems. This paper contends that a large proportion of the ensuing demands can be satisfied by an iterative and incremental development model revolving around two evolutionary enhancements to the present engineering approach, namely (1) static real‐time analysis as a key ingredient of the software verification process, and (2) an architectural paradigm centred on fixed priority preemptive scheduling. Copyright © 1999 John Wiley & Sons, Ltd.     

Experiences with EDO: An evolutionary database optimizer

In this paper we introduce the database design tool EDO: an Evolutionary Database Optimizer. The term ‘evolutionary’ refers to a basic feature of the tool. After generating an initial pool of preliminary internal representations for a given conceptual data model, EDO allows a database designer to activate evolution strategies, modifying the preliminary internal representations into more desirable ones.

The quality of the internal representations found as yet is used to perform a guided walk through the solution space of alternative internal representations for the conceptual model under consideration. This quality (called fitness) takes into account the expected storage space and the expected average response time of a candidate internal representation.     

Genetic algorithms for optimal logical database design

The focus of this paper is database design using automated database design tools or more general CASE tools. We present a genetic algorithm for the optimization of (internal) database structures, using a multi-criterion objective function. This function expresses conflicting objectives, reflecting the well-known time/space trade-off. This paper shows how the solution space of the algorithm can be set up in the form of tree structures (forests), and how these are encoded by a simple integer assignation. Genetic operators (database transformations) defined in terms of this encoding behave as if they manipulate tree structures. Some basic experimental results produced by a research prototype are presented.