Optimal representation of cycles in arithmetic graphs

The paper considers representation of Hamiltonian circuits by natural arithmetic graphs.Translated from Kibernetika, No. 1, pp. 17–20, January–February, 1991.     

Application of the graph planarity test in computer-aided circuit design

A generalized graph planarity test is constructed for graphs with cyclic ordering of the edges incident on some of the vertices in the sought planar embedding. The results are applied to computer-aided design of computer circuits.Translated from Kibernetika, No. 2, pp. 37–41, March–April, 1989.     

Systolic array implementation of some iterative algorithms for solving systems of linear algebraic equations

The paper elucidates the internal properties of some iterative linear algebra algorithms through transformation of their lattice graphs.Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 145–158, September–October, 1992.     

Lattices of processes in graphs and congruences on ideals in distributive lattices

We consider the class of lattices of processes in graphs and its relationship to the class of all distributive lattices.Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 162–165, January–February, 1992.     

NP-completeness of maximum-cut and cycle-covering problems for a planar graph

We consider problems of finding the maximum cut and a cycle covering for a planar graph with edge weights of arbitrary sign. Methods that find the maximum cut in graphs with only positive edge weights are shown to be inapplicable in this case. NP-completeness of the problem is proved.Translated from Kibernetika, No. 1, pp. 13–16, January–February, 1991.     

Restrictions of Minimum Spanner Problems

At-spanner of a graphGis a spanning subgraphHsuch that the distance between any two vertices inHis at mostttimes their distance inG. Spanners arise in the context of approximating the original graph with a sparse subgraph (Peleg, D., and Schäffer, A. A. (1989),J. Graph. Theory13(1), 99–116). The MINIMUMt-SPANNER problem seeks to find at-spanner with the minimum number of edges for the given graph. In this paper, we completely settle the complexity status of this problem for various values oft, on chordal graphs, split graphs, bipartite graphs and convex bipartite graphs. Our results settle an open question raised by L. Cai (1994,Discrete Appl. Math.48, 187–194) and also greatly simplify some of the proofs presented by Cai and by L. Cai and M. Keil (1994,Networks24, 233–249). We also give a factor 2 approximation algorithm for the MINIMUM 2-SPANNER problem on interval graphs. Finally, we provide approximation algorithms for the bandwidth minimization problem on convex bipartite graphs and split graphs using the notion of tree spanners.     

Coding and counting spanning trees in Kleitman-Golden graphs

Spanning trees of squares (in Harary's sense) of simple chains and simple cycles are coded by words in a three-letter alphabet. Counting of spanning trees in these graphs is reduced to counting of code words by the generating function method for ordered partitions.Translated from Kibernetika, No. 3, pp. 1–7, May–June, 1991.     

ω-Perfect graphs

-Perfect graph is defined and some classes of -perfect graphs are described, although the characterization of the complete class of -perfect graphs remains an open question. A bound on the chromatic number for graphs without even holes is derived.Translated from Kibernetika, No. 2, pp. 8–11, March–April, 1990.     

Optimal algorithms for the identification of system states based on three-valued logic

Conclusions Optimal algorithms, in the sense of minimum volume of processed information, have been proposed for state identification in systems, represented by ordered logical-function graphs as optimal system models. These same algorithms are suboptimal for nonplanar graphs. The use of optimal algorithms assures high efficiency of the processes connected with the classification of the system elements by three attributes, observed at the output. In the identification of the location of a failure in a technical system, as a particular case, a manyfold acceleration of this process has been achieved, the requirements on the qualifications of the specialists have been reduced, while computerization has provided practically instantaneous solution of this problem.Translated from Kibernetika, No. 2, pp. 1–6, March–April, 1976.     

Node overlap removal in clustered directed acyclic graphs

Graph drawing and visualization represent structural information as diagrams of abstract graphs and networks. An important subset of graphs is directed acyclic graphs (DAGs). This paper presents a new E-Spring algorithm, extended from the popular spring embedder model, which eliminates node overlaps in clustered DAGs. In this framework, nodes are modeled as non-uniform charged particles with weights, and a final drawing is derived by adjusting the positions of the nodes according to a combination of spring forces and repulsive forces derived from electrostatic forces between the nodes. The drawing process needs to reach a stable state when the average distances of separation between nodes are near optimal. We introduce a stopping condition for such a stable state, which reduces equilibrium distances between nodes and therefore results in a significantly reduced area for DAG visualization. It imposes an upper bound on the repulsive forces between nodes based on graph geometry. The algorithm employs node interleaving to eliminate any residual node overlaps. These new techniques have been validated by visualizing eBay buyer–seller relationships and has resulted in overall area reductions in the range of 45–79%.     

Deduction Graphs with Universal Quantification

Deduction Graphs are meant to generalise both Gentzen-Prawitz style natural deductions and Fitch style flag deductions. They have the structure of acyclic directed graphs with boxes. In [Herman Geuvers and Iris Loeb. Natural Deduction via Graphs: Formal Definition and Computation Rules. Mathematical Structures in Computer Science (Special Issue on Theory and Applications of Term Graph Rewriting), Volume 17(03):485–526, 2007.] we have investigated the deduction graphs for minimal proposition logic. This paper studies the extension with first-order universal quantification, showing the robustness of the concept of deduction graphs.     

Thermodynamic assessments of binary phase diagrams in organic and polymeric systems

The Sanchez–Lacombe (SL) model and the Flory–Huggins model were used for the calculation of binary phase diagrams in organic and polymer systems, respectively. The thermodynamic parameters of the liquid and gas phases in acetone–carbon disulfide (CS₂), butane–heptane, cyclohexane–aniline systems, and liquid phases in polystyrene–polybutadiene and polystyrene–bisphenol A poly-carbonate systems were optimized, based on the experimental data. The calculated results with various pressures are in good agreement with the experimental data. It is hoped that this method will be widely applied in the prediction of binary phase diagrams in organic and polymer systems.     

Structural analysis of local search heuristics in combinatorial optimization

Neighborhood, or local, search is a popular and practical heuristic for many combinational optimization problems. We examine the neighborhood structures of two classes of problems, 0–1 integer programming and the mean tardiness job sequencing problem—from the viewpoint of state-space graphs in artificial intelligence. Such analysis is shown to provide fundamental insights into the nature of local search algorithms and provides a useful framework for evaluating and comparing such heuristics. Computational results are presented to support these observations.     

A cross model study of corporate financial distress prediction in Taiwan: Multiple discriminant analysis, logit, probit and neural networks models

In 2008, financial tsunami started to impair the economic development of many countries, including Taiwan. The prediction of financial crisis turns to be much more important and doubtlessly holds public attention when the world economy goes to depression. This study examined the predictive ability of the four most commonly used financial distress prediction models and thus constructed reliable failure prediction models for public industrial firms in Taiwan. Multiple discriminate analysis (MDA), logit, probit, and artificial neural networks (ANNs) methodology were employed to a dataset of matched sample of failed and non-failed Taiwan public industrial firms during 1998–2005. The final models are validated using within sample test and out-of-the-sample test, respectively. The results indicated that the probit, logit, and ANN models which used in this study achieve higher prediction accuracy and possess the ability of generalization. The probit model possesses the best and stable performance. However, if the data does not satisfy the assumptions of the statistical approach, then the ANN approach would demonstrate its advantage and achieve higher prediction accuracy. In addition, the models which used in this study achieve higher prediction accuracy and possess the ability of generalization than those of [Altman, Financial ratios—discriminant analysis and the prediction of corporate bankruptcy using capital market data, Journal of Finance 23 (4) (1968) 589–609, Ohlson, Financial ratios and the probability prediction of bankruptcy, Journal of Accounting Research 18 (1) (1980) 109–131, and Zmijewski, Methodological issues related to the estimation of financial distress prediction models, Journal of Accounting Research 22 (1984) 59–82]. In summary, the models used in this study can be used to assist investors, creditors, managers, auditors, and regulatory agencies in Taiwan to predict the probability of business failure.     

Shaped lattice graphs as models of the multiprocessor computer systems

A new family of the uniform ordinary graphs named the shaped lattice graphs was proposed and studied. As applied to the structural modeling of the multiprocessor computer systems, they have two useful characteristics such as high flexibility at choosing their size (number of vertices) and possibility of obtaining small (down to d = 2) diameters independently of the graph size. The method of cycle definition and transformation by the ring sequences of edge weights, which was previously proposed for the binary hypercubes and other Cayley graphs, was extended to the shaped lattice graphs.Translated from Avtomatika i Telemekhanika, No. 3, 2005, pp. 169–180.Original Russian Text Copyright © 2005 by Parkhomenko.This paper was recommended for publication by P.Yu. Chebotarev, a member of the Editorial Board     

Algorithm of Extrapolation of a Nonlinear Random Process on the Basis of Its Canonical Decomposition

Based on the apparatus of canonical decompositions, an algorithm of extrapolation of a nonlinear random process is obtained for an arbitrary number of known values and probabilistic relations used for a prediction.__________Translated from Kibernetika i Sistemnyi Analiz, No.2, pp. 131–139, March–April 2005.     

Learnability and Definability in Trees and Similar Structures

We prove upper bounds for combinatorial parameters of finite relational structures, related to the complexity of learning a definable set. We show that monadic second-order (MSO) formulas with parameters have bounded Vapnik–Chervonenkis dimension over structures of bounded clique-width, and first-order formulas with parameters have bounded Vapnik–Chervonenkis dimension over structures of bounded local clique-width (this includes planar graphs). We also show that MSO formulas of a fixed size have bounded strong consistency dimension over MSO formulas of a fixed larger size, for labeled trees. These bounds imply positive learnability results for the PAC and equivalence query learnability of a definable set over these structures. The proofs are based on bounds for related definability problems for tree automata.     

A local space–time kriging approach applied to a national outpatient malaria data set

Increases in the availability of reliable health data are widely recognised as essential for efforts to strengthen health-care systems in resource-poor settings worldwide. Effective health-system planning requires comprehensive and up-to-date information on a range of health metrics and this requirement is generally addressed by a Health Management Information System (HMIS) that coordinates the routine collection of data at individual health facilities and their compilation into national databases. In many resource-poor settings, these systems are inadequate and national databases often contain only a small proportion of the expected records. In this paper, we take an important health metric in Kenya (the proportion of outpatient treatments for malaria (MP)) from the national HMIS database and predict the values of MP at facilities where monthly records are missing. The available MP data were densely distributed across a spatiotemporal domain and displayed second-order heterogeneity. We used three different kriging methodologies to make cross-validation predictions of MP in order to test the effect on prediction accuracy of (a) the extension of a spatial-only to a space–time prediction approach, and (b) the replacement of a globally stationary with a locally varying random function model. Space–time kriging was found to produce predictions with 98.4% less mean bias and 14.8% smaller mean imprecision than conventional spatial-only kriging. A modification of space–time kriging that allowed space–time variograms to be recalculated for every prediction location within a spatially local neighbourhood resulted in a larger decrease in mean imprecision over ordinary kriging (18.3%) although the mean bias was reduced less (87.5%).     

Strategies for interconnection networks: Some methods from graph theory

Interconnection networks require dense graphs in the sense that many nodes with relatively few links may be connected with relatively short paths. Some recent constructions of such dense graphs with a given maximal degree Δ and diameter D (known as (Δ, D) graphs) are reviewed here. The paper also contains an updated table of the best known (Δ, D) graphs.     

Steady state analysis and computation of the GI/M/1/L queue with multiple working vacations and partial batch rejection

This paper analyzes a finite-buffer bulk-arrival bulk-service queueing system with multiple working vacations and partial batch rejection in which the inter-arrival and service times are, respectively, arbitrarily and exponentially distributed. Using the supplementary variable and the embedded Markov chain techniques, we obtain the waiting queue-length distributions at pre-arrival and arbitrary epochs. We also present Laplace–Stiltjes transform of the actual waiting-time distribution in the queue. Finally, several performance measures and a variety of numerical results in the form of tables and graphs are discussed.