Wyniki wyszukiwania - BazTech

1

Unfoldings and Coverings of Weighted Graphs

Courcelle Bruno

Fundamenta Informaticae

|

2022

|

Vol. 189, nr 1.

1--47

EN

Coverings of undirected graphs are used in distributed computing, and unfoldings of directed graphs in semantics of programs. We study these two notions from a graph theoretical point of view so as to highlight their similarities, as they are both defined in terms of surjective graph homomorphisms. In particular, universal coverings and complete unfoldings are infinite trees that are regular if the initial graphs are finite. Regularity means that a tree has finitely many subtrees up to isomorphism. Two important theorems have been established by Leighton and Norris for coverings of finite graphs. We prove similar results for unfoldings of finite directed graphs. Moreover, we generalize coverings and similarly, unfoldings to graphs and digraphs equipped with finite or infinite weights attached to edges of the covered or unfolded graphs. This generalization yields a canonical "factorization" of the universal covering of any finite graph, that (provably) does not exist without using weights. Introducing ω as an infinite weight provides us with finite descriptions of regular trees having nodes of countably infinite degree. Regular trees (trees having finitely many subtrees up to isomorphism) play an important role in the extension of Formal Language Theory to infinite structures described in finitary ways. Our weighted graphs offer effective descriptions of the above mentioned regular trees and yield decidability results. We also generalize to weighted graphs and their coverings a classical factorization theorem of their characteristic polynomials.

2

On the weightedk-path vertex cover on interval graphs

Zygadło Jakub

Schedae Informaticae

|

2020

|

Vol. 29

9--21

EN

We consider a version of the k-path vertex cover problem that asks for the minimum weight subset C of vertices of a graph G such that every path on k vertices in G has at least one vertex in common with C. We present two dynamic algorithms solving this problem on interval graphs. The first one works on general interval graphs but is in practice limited to small values of k. The second algorithm computes minimum weight vertex cover for arbitrary k on proper interval graph G = (V,E) in time O(|V|^2|E|).

3

Computational Classification of Tubular Algebras

Dowbor Piotr, Kim Yan

Fundamenta Informaticae

|

2020

|

Vol. 177, nr 1

39--67

EN

The effective method (based on Theorem 5.3) of classifying tubular algebras by the Cartan matrices of tilting sheaves over weighted projective lines with all indecomposable direct summands in some finite “fundamental domain” , by the reduction to the two elementary problems of discrete mathematics having algorithmic solutions is presented in details (see Problem A and B). The software package CART_TUB being an implementation of this method yields the precise classification of all up to isomorphism tubular algebras of a fixed tubular type p, by creating the complete lists of their Cartan matrices, and furnish their tilting realizations. In particular, the number of isomorphism classes of tubular algebras of the type p is determined (Theorem 2.3).

4

Lightweight paths in graphs

Harant Jochen, Jendrol Stanislav

Opuscula Mathematica

|

2019

|

Vol. 39, no. 6

829--837

EN

Let k be a positive integer, G be a graph on V(G) containing a path on k vertices, and w be a weight function assigning each vertex v ∈ V(G) a real weight w(y). Upper bounds on the weight [formula] of P are presented, where P is chosen among all paths of G on k vertices with smallest weight.

5

The Weighted Matching Approach to Maximum Cardinality Matching

Gabow H. N.

Fundamenta Informaticae

|

2017

|

Vol. 154, nr 1/4

109--130

EN

Several papers have achieved time O(√nm) for cardinality matching, starting from first principles. This results in a long derivation. We simplify the task by employing well-known concepts for maximum weight matching. We use Edmonds’ algorithm to derive the structure of shortest augmenting paths. We extend this to a complete algorithm for maximum cardinality matching in time O(√nm).

6

Game-Theoretic Centrality Measures for Weighted Graphs

Mazalov V. V., Trukhina L. I., Avrachenkov K. E., Tsynguev B. T.

Fundamenta Informaticae

|

2016

|

Vol. 145, nr 3

341--358

EN

The betweenness centrality is one of the basic concepts in the analysis of the social networks. Initial definition for the betweenness of a node in the graph is based on the fraction of the number of geodesics (shortest paths) between any two nodes that given node lies on, to the total number of the shortest paths connecting these nodes. This method has polynomial complexity. We propose a new concept of the betweenness centrality for weighted graphs using the methods of cooperative game theory. The characteristic function is determined by special way for different coalitions (subsets of the graph). Two approaches are used to determine the characteristic function. In the first approach the characteristic function is determined via the number of direct and indirect weighted connecting paths in the coalition. In the second approach the coalition is considered as an electric network and the characteristic function is determined as a total current in this network. We use the Kirchhoff's law. After that the betweenness centrality is determined as the Myerson value. The results of computer simulations for some examples of networks, in particular, for the popular social network "VKontakte", as well as the comparing with the PageRank method are presented.

7

Frames and factorization of graph Laplacians

Jorgensen P., Tian F.

Opuscula Mathematica

|

2015

|

Vol. 35, no. 3

293--332

EN

Using functions from electrical networks (graphs with resistors assigned to edges), we prove existence (with explicit formulas) of a canonical Parseval frame in the energy Hilbert space [formula] of a prescribed infinite (or finite) network. Outside degenerate cases, our Parseval frame is not an orthonormal basis. We apply our frame to prove a number of explicit results: With our Parseval frame and related closable operators in [formula] we characterize the Priedrichs extension of the [formula]-graph Laplacian. We consider infinite connected network-graphs G = (V, E), V for vertices, and E for edges. To every conductance function c on the edges E of G, there is an associated pair [formula] where [formula] in an energy Hilbert space, and Δ (=Δc) is the c-graph Laplacian; both depending on the choice of conductance function c. When a conductance function is given, there is a current-induced orientation on the set of edges and an associated natural Parseval frame in [formula] consisting of dipoles. Now Δ is a well-defined semibounded Hermitian operator in both of the Hilbert [formula] and [formula]. It is known to automatically be essentially selfadjoint as an [formula]-operator, but generally not as an [formula] operator. Hence as an [formula] operator it has a Friedrichs extension. In this paper we offer two results for the Priedrichs extension: a characterization and a factorization. The latter is via [formula].

8

Optymalizacja trasy podróży turystycznej samochodem elektrycznym

Karbowska-Chilińska J., Zabielski P.

Symulacja w Badaniach i Rozwoju

|

2014

|

Vol. 5, nr 2

81--94

PL

Samochód elektryczny jest zeroemisyjny, bardzo cichy i tani w eksploatacji. Może być wykorzystywany zarówno jako samochód miejski, jak i w podróżowaniu turystycznym. W artykule przedstawiamy algorytm, który zaplanuje trasę wycieczki w taki sposób, żeby odwiedzone zostały najatrakcyjniejsze obiekty turystyczne, oraz uwzględni w punkcie początkowym i końcowym trasy ładowanie baterii. Atrakcyjność obiektu jest wyznaczana na podstawie opinii internatów o danym obiekcie. Maksymalna długość wycieczki to liczba kilometrów, jakie samochód może przejechać na jednym ładowaniu baterii. Zaproponowany przez autorów algorytm ewolucyjny został przetestowany na rzeczywistych danych, obejmujących obiekty turystyczne i stacje ładowania baterii na Podlasiu. Czas działania algorytmu oraz wyniki testów wykazują, że opisany algorytm może być częścią modułu oprogramowania stosowanego w samochodach elektrycznych lub aplikacją na smartfony, która ułatwia i uprzyjemnia podróżowanie, a jednocześnie pozwala optymalnie wykorzystać energię samochodu elektrycznego.

EN

Electric vehicle (EV) does not emit harmful gases, it is very quiet and cheap to use. It can be used both as a city car and in the travel tourism. In this paper we present an algorithm that will plan a route of electric vehicle in such a way that the most attractive tourist points of interest are visited and takes into account the starting point and the final point of a route as a EV charging station. Attractiveness of points of interest is determined on the basis of a ranking on the internet. The maximum length of the tour is determined by the number of kilometres that the car can travel on a single battery charge. The evolutionary algorithm proposed by us was tested on realistic database points of interests and EV charging stations in Podlasie region. On the basis of the tests results and execution times of the algorithm we conclude that the proposed algorithm could be a part of a software module in EV or an application for smart phones which makes traveling easier and more comfortable. Moreover EV battery power is used optimally.

9

The Local Importance of Node in Complex Networks

Xiao L., Chen L., Xiao J.

Przegląd Elektrotechniczny

|

2013

|

R. 89, nr 1b

236--238

EN

This paper presents a new weighted graph to represent the strength of relationships between nodes, this graph can be a direct reflection of the interaction frequency of interconnected nodes, through the calculation of the weights, it can measure the local importance of the node results show that the local importance of a node is proportional to the degree of the node and the interaction frequency of the node. Under certain conditions, the local importance is inversely proportional to the degree of its adjacent nodes.

PL

W artykule przedstawiono nowy diagram ważony do prezentacji siły relacji między korzeniami sieci. Graf może być bezpośrednim odbiciem wzajemnych oddziaływać częstotliwościowych współpracujących korzeni. Poprzez obliczenia wag może oceniać znaczenie korzenia lokalnego. Wyniki wskazują, że znaczenie korzenia lokalnego jest proporcjonalne do stopnia korzenia i częstotliwości współpracy. W szczególnych warunkach lokalne znaczenie jest odwrotnie proporcjonalne do stopnie korzenia przylegającego.

10

A sampling theory for infinite weighted graphs

Jorgensen P. E. T.

Opuscula Mathematica

|

2011

|

Vol. 31, no. 2

209-236

EN

We prove two sampling theorems for infinite (countable discrete) weighted graphs G; one example being "large grids of resistors" i.e., networks and systems of resistors. We show that there is natural ambient continuum X containing G, and there are Hilbert spaces of functions on X that allow interpolation by sampling values of the functions restricted only on the vertices in G. We sample functions on X from their discrete values picked in the vertex-subset G. We prove two theorems that allow for such realistic ambient spaces X for a fixed graph G, and for interpolation kernels in function Hilbert spaces on X, sampling only from points in the subset of vertices in G. A continuum is often not apparent at the outset from the given graph G. We will solve this problem with the use of ideas from stochastic integration.

11

Improved state encoding for FSM implementation in FPGA structures with embedded memory blocks

Borowik G.

Electronics and Telecommunications Quarterly

|

2008

|

Vol. 54, No 1

9-28

EN

Modern FPLD devices have a very complex structure. They combine PLA-like structures as well as FPGA's and even memory-based structures. However, the lack of an appropriate synthesis method does not allow the features of the modern FPLD's to be fully exploited. In this paper, an important problem of state assignment for an FSM as an extension of the previous research on ROM-based FSM implementation is presented. We pinpoint the sources of additional optimization of the functional decomposition and relate them to the state encoding conditions. The method is based on a reduction of a state assignment problem to a graph coloring problem. To this end, the so called multi-graph of incompatibility of memory T-words is applied. As a result, a new design technique for implementation of sequential circuits using embedded memory blocks of FPGA's has been developed. Preliminary experimental results- are extremely encouraging.

12

Wyznaczanie połączeń w sieciach komunikacyjnych o zmiennych wagach

Widuch J.

Studia Informatica

|

2002

|

Vol. 23, nr 4

85-104

PL

Problem wyznaczania połączeń w sieciach komunikacyjnych jest przykładem optymalizacji wielokryterialnej. Rozwiązaniem problemu optymalizacji wielokryterialnej jest zbiór rozwiązań niezdominowanych. Wyznaczenie połączeń polega na rozwiązaniu dwukryterialnego problemu najkrótszych ścieżek w grafie ważonym o zmiennych wagach. W pracy przedstawiono algorytm umożliwiający wyznaczenie wszystkich połączeń należących do zbioru rozwiązań niezdominowanych. Zaprezentowano także przykładowe wyniki działania algorytmu. Oprócz tego przedstawiono dwa algorytmy rozwiązujące dwukryterialny problem najkrótszych ścieżek w grafie ważonym o stałych wagach.

EN

The communication networks routing problem is an example of mulitcriteria optimization. The solution to a multicriteria optimization problem is the set of non-dominated solutions. Establishing routes consists in solving the bicriterion shortest path problem in the weighted graph with non-constant weights. In the paper an algorithm which determines all routes which belong to the set of non-dominated solutions is shown. The result of the tests are also presented. In addition, two algorithms for solving the bicriterion shortest path problem in a weighted graph with constant weights are presented.

13

Analysis of fractal operator convergence by graph methods

Skarbek W.

Fundamenta Informaticae

|

1998

|

Vol. 34, nr 4

429-440

EN

The convergence of fractal operator F used in image compression is investigated by analysis of block influence graph and pixel influence graph. The graph stability condition in block influence graph implies eventual contractivity condition which is sufficient for the operator iteration convergence. The graph stability condition in pixel influence graph appears to be sufficient and necessary for convergence of selecting fractal operators.