On the Vertex Separation of Cactus Graphs

This paper is part of a work in progress whose goal is to construct a fast, practical algorithm for the vertex separation (VS) of cactus graphs. We prove a \main theorem for cacti", a necessary and sufficient condition for the VS of a cactus graph being k. Further, we investigate the ensuing ramifications that prevent the construction of an algorithm based on that theorem only.

Algorithmic Background of the Host Recommendation in the Adaptive Distributed Multimedia Server

Partial support of the Hungarian State Eötvös Scholarship, the Hungarian National Science Fund (Grant No. OTKA 42559 and 42706) and the Mobile Innovation Center, Hungary is gratefully acknowledged.

FLQ, the Fastest Quadratic Complexity Bound on the Values of Positive Roots of Polynomials

In this paper we present F LQ, a quadratic complexity bound on the values of the positive roots of polynomials. This bound is an extension of FirstLambda, the corresponding linear complexity bound and, consequently, it is derived from Theorem 3 below. We have implemented FLQ in the Vincent-Akritas-Strzeboński Continued Fractions method (VAS-CF) for the isolation of real roots of polynomials and compared its behavior with that of the theoretically proven best bound, LM Q. Experimental results indicate that whereas F LQ runs on average faster (or quite faster) than LM Q, nonetheless the quality of the bounds computed by both is about the same; moreover, it was revealed that when VAS-CF is run on our benchmark polynomials using F LQ, LM Q and min(F LQ, LM Q) all three versions run equally well and, hence, it is inconclusive which one should be used in the VAS-CF method.

On the Vertex Separation of Maximal Outerplanar Graphs

We investigate the NP-complete problem Vertex Separation (VS) on Maximal Outerplanar Graphs (mops). We formulate and prove a “main theorem for mops”, a necessary and sufficient condition for the vertex separation of a mop being k. The main theorem reduces the vertex separation of mops to a special kind of stretchability, one that we call affixability, of submops.

The Point of Continuity Property: Descriptive Complexity and Ordinal Index

∗ Supported by D.G.I.C.Y.T. Project No. PB93-1142

Enhancing the performance of intelligent control systems in the face of higher levels of complexity and uncertainty

Modern advances in technology have led to more complex manufacturing processes whose success centres on the ability to control these processes with a very high level of accuracy. Plant complexity inevitably leads to poor models that exhibit a high degree of parametric or functional uncertainty. The situation becomes even more complex if the plant to be controlled is characterised by a multivalued function or even if it exhibits a number of modes of behaviour during its operation. Since an intelligent controller is expected to operate and guarantee the best performance where complexity and uncertainty coexist and interact, control engineers and theorists have recently developed new control techniques under the framework of intelligent control to enhance the performance of the controller for more complex and uncertain plants. These techniques are based on incorporating model uncertainty. The newly developed control algorithms for incorporating model uncertainty are proven to give more accurate control results under uncertain conditions. In this paper, we survey some approaches that appear to be promising for enhancing the performance of intelligent control systems in the face of higher levels of complexity and uncertainty.

Quasi-Monte Carlo Methods for some Linear Algebra Problems. Convergence and Complexity

We present quasi-Monte Carlo analogs of Monte Carlo methods for some linear algebra problems: solving systems of linear equations, computing extreme eigenvalues, and matrix inversion. Reformulating the problems as solving integral equations with a special kernels and domains permits us to analyze the quasi-Monte Carlo methods with bounds from numerical integration. Standard Monte Carlo methods for integration provide a convergence rate of O(N^(−1/2)) using N samples. Quasi-Monte Carlo methods use quasirandom sequences with the resulting convergence rate for numerical integration as good as O((logN)^k)N^(−1)). We have shown theoretically and through numerical tests that the use of quasirandom sequences improves both the magnitude of the error and the convergence rate of the considered Monte Carlo methods. We also analyze the complexity of considered quasi-Monte Carlo algorithms and compare them to the complexity of the analogous Monte Carlo and deterministic algorithms.

An Algorithmic Solution for Management of Related Text Objects with Application in Phytopharmacy

This paper presents an algorithmic solution for management of related text objects, in which are integrated algorithms for their extraction from paper or electronic format, for their storage and processing in a relational database. The developed algorithms for data extraction and data analysis enable one to find specific features and relations between the text objects from the database. The algorithmic solution is applied to data from the field of phytopharmacy in Bulgaria. It can be used as a tool and methodology for other subject areas where there are complex relationships between text objects.

A Linear Time Algorithm for Computing Longest Paths in Cactus Graphs

ACM Computing Classification System (1998): G.2.2.

An Algorithmic Approach to Inferring Cross-Ontology Links while Mapping Anatomical Ontologies

ACM Computing Classification System (1998): J.3.

Developing Students’ Mathematical Thinking and Algorithmic Culture in IT Classes

Report published in the Proceedings of the National Conference on "Education in the Information Society", Plovdiv, May, 2012

Algorithmic Methods in Queues and in the Exploration of Point Processes

This is a review of methodology for the algorithmic study of some useful models in point process and queueing theory, as discussed in three lectures at the Summer Institute at Sozopol, Bulgaria. We provide references to sources where the extensive details of this work are found. For future investigation, some open problems and new methodological approaches are proposed.

On the Time Complexity of the Problem Related to Reducts of Consistent Decision Tables

In recent years, rough set approach computing issues concerning reducts of decision tables have attracted the attention of many researchers. In this paper, we present the time complexity of an algorithm computing reducts of decision tables by relational database approach. Let DS = (U, C ∪ {d}) be a consistent decision table, we say that A ⊆ C is a relative reduct of DS if A contains a reduct of DS. Let s = be a relation schema on the attribute set C ∪ {d}, we say that A ⊆ C is a relative minimal set of the attribute d if A contains a minimal set of d. Let Qd be the family of all relative reducts of DS, and Pd be the family of all relative minimal sets of the attribute d on s. We prove that the problem whether Qd ⊆ Pd is co-NP-complete. However, the problem whether Pd ⊆ Qd is in P .

A question of complexity:measuring the maturity of online enquiry communities

Online enquiry communities such as Question Answering (Q&A) websites allow people to seek answers to all kind of questions. With the growing popularity of such platforms, it is important for community managers to constantly monitor the performance of their communities. Although different metrics have been proposed for tracking the evolution of such communities, maturity, the process in which communities become more topic proficient over time, has been largely ignored despite its potential to help in identifying robust communities. In this paper, we interpret community maturity as the proportion of complex questions in a community at a given time. We use the Server Fault (SF) community, a Question Answering (Q&A) community of system administrators, as our case study and perform analysis on question complexity, the level of expertise required to answer a question. We show that question complexity depends on both the length of involvement and the level of contributions of the users who post questions within their community. We extract features relating to askers, answerers, questions and answers, and analyse which features are strongly correlated with question complexity. Although our findings highlight the difficulty of automatically identifying question complexity, we found that complexity is more influenced by both the topical focus and the length of community involvement of askers. Following the identification of question complexity, we define a measure of maturity and analyse the evolution of different topical communities. Our results show that different topical communities show different maturity patterns. Some communities show a high maturity at the beginning while others exhibit slow maturity rate. Copyright 2013 ACM.

Impact of reduced complexity inverse Volterra series transfer function-based nonlinear equalizer in coherent OFDM systems for next-generation core networks

A modern electronic nonlinearity equalizer (NLE) based on inverse Volterra series transfer function (IVSTF) with reduced complexity is applied on coherent optical orthogonal frequency-division multiplexing (CO-OFDM) signals for next-generation long- and ultra-long-haul applications. The OFDM inter-subcarrier crosstalk effects are explored thoroughly using the IVSTF-NLE and compared with the case of linear equalization (LE) for transmission distances of up to 7000 km. © 2013 IEEE.