Hierarchical approach for drawing directed graphs
This article is a review of the methodology for automatic drawing of arbitrary
directed graphs. Layered drawings with edges following one common direction
are used to emphasize the hierarchy of vertices in such graphs. The approach
described in this article is usually divided into three steps.
- Assignment of the vertices to layers so that all edges point to one direction.
- For each layer, an ordering of the vertices is computed in order to minimize the number of edge crossings.
- Coordinate assignment of vertices in the layer in order to minimize the total edge length and the number of edge bends.
The review contains a detailed description of each step of the algorithm. The
author presents different solutions to the problems arising at each stage, gives
references to original papers, and also compares these solutions in terms of
satisfying aesthetic criteria and time complexity. The review also covers the
related topics (edge and vertex labeling, dynamic layouts, open problems) and a
number of methods to convert an arbitrary graph to a directed one.
Methods and techniques of adaptive hypermedia
Adaptive hypermedia is a relatively new research direction at the junction of
hypermedia and user modeling. Adaptive hypermedia systems build a user model
on the basis of goals, knowledge, preferences, and other characteristics of each
particular user, and use this model when interacting with the user in order to
adapt to his/her needs. This paper provides a brief survey of existing methods and
techniques of adaptive content presentation and adaptive navigation support.
Translating components of a functional programming system (SFP)
The paper describes a system of functional programming (SFP) and its components:
translator, debugging tools, internal representation of Sisal-programs, Sisal-to-C
converter. Testing of SFP's translating components is also described.
Algorithms of fast search for fragments of photoimages
Search for fragments in images is an actual problem arising in many fields of
human activity. It is desirable to perform it with maximal speed.
The aim of this work is to construct algorithms and programs that find a particular
fragment in an image. The program here described consists of two parts: a
computational kernel and a control shell that works as a user interface.
The main advantage of this new approach is the fact that all fragments are in a
simultaneous search. This algorithm is one of the best in the world.
This article is devoted to the methods of decision making in the theory for
solving the inventive problems (TRIZ) and their application to the problem
of conflict resolution. The algorithm of solving the inventive problems (ARIZ)
and its analogue for resolution of conflict situations (ARPS) are considered. A
graphical interface of TRIZ_Computing intended for conflict analysis is described.
The program presents several examples.
Computer-aided decision making at the railway transport as a guarantee of railway safety
This article presents ARMs TCHB systems (ARMNaradchick, ARMZAVbrigadami).
ARM TCHB is implemented within the framework of ASUT (locomotive facilities
automated control system) concept developed in the Application Center of Ministry
of Railways in collaboration with VNIIZhT, VNIIAS, West-Siberian and Moscow
railways and other railway enterprises by instruction of the Department of locomotive
The main purpose of the system is to completely exclude mistakes of operating
personnel during formation and work of locomotive brigades and engine drivers
working as one person. The system is also intended for optimization of managing
the locomotive brigades. Another task (which is not of less importance) of ARM
TCHB (conjugate with ARM TCHD) is computer-aided preparating and sending
reports on disposition and state of brigades to OKDB system in a real-time
A pipeline model of transportation as a model of message passing
We show that the transportation problem with a pipeline model is the closest to
the problem with a "wormlike" model of message passing..
The development of NUMA-architectures: current state
The aim of this paper is to consider the dynamic of development of NUMAarchitectures
in the last decade.
A review of MPEG-like methods of video data encoding
The basic methods of video data encoding used in MPEG-like formats are considered,
such as a search for motion vectors, encoding of residual image, and encoding of
Virtual museum of informatics history in Siberia
The paper presents the project of a virtual museum of informatics history in
Siberia. The Siberian informatics and programming school is briefly described,
the structure, contents and user interface of the virtual museum are considered,
and adaptive hypermedia problems are studied.
User interface of an integrated functional programming environment SFP
The paper is devoted to a part of a project on creation of IFPE (integrated
functional programming environment) for the functional programming language
Sisal. It describes the user interface of IFPE and some of its components, such
as editor, translator, etc.
IS TRANSFORM: computer-aided system filling
This paper focuses on the current state of IS TRANSFORM and possible ways of
extending its features. It also considers the methods of autoindexing and possible
approaches to the decision of the problem of adequate autoindexing of documents
and extracting information from them.
A project of a system for fast prototyping of a parallelizing compiler. Generalpurpose internal system representation
The first part of this paper presents a project of a research-and-training system
for fast prototyping of the parallelizing compiler. It contains the tasks set to the
system and shows how they relate to the process of compiler development. The
architecture of the system is described together with its constituents working
at certain stages of compilation and its main components, such as a scalable
universal internal form (IF), "scenario" and the "scenario" language. In the second
part of the paper, IF of the system, its "language" and "graph" components are
considered in detail. Some new concepts are introduced, namely, the abstract
syntactical graph and graph shadows for investigation of various internal graphtheoretical
forms of programs.
Path kernel and cycle length in undirected graphs
Let τ(G) denote the number of vertices in the longest path of a graph G. A subset
K of the set of vertices V of the graph G is called Pn-kernel of the graph G, if τ(G[K]) ≤ n-1 and every vertex x ∈ V (G\K) are adjacent to the terminal
vertex of the path of length n in the graph G. Here the theorem on existence of
a Pn-kernel of the graph G with the length of the maximal cycle n-2 has been
Real-time tracking and velocity determination of objects moving on a plane
A logical module is discussed in the paper for a real-time object tracking system.
Images obtained by a fixed video camera are used as input data. The output is
information about objects viewed by the camera. A usual Pentium-2 computer
is used as the hardware part.
Optimal data distribution in information systems according to the system component reliability
The article is devoted to the problem of optimal data distribution in information
systems for the case of a distributed client-server system. The method of optimal
distribution of tables is described. The proposed approach considers not only
the system's component performance and data channel utilization, but also the
system reliability. It is possible to use this method in the computation system