Wyniki wyszukiwania - BazTech

1

A note on bipartite graphs whose [1, k]-domination number equal to their number of vertices

Ghareghani Narges, Peterin Iztok, Sharifani Pouyeh

Opuscula Mathematica

|

2020

|

Vol. 40, no. 3

375--382

EN

A subset D of the vertex set V of a graph G is called an [1, k]-dominating set if every vertex from V — D is adjacent to at least one vertex and at most fc vertices of D. A [1, k]-dominating set with the minimum number of vertices is called a [formula]-set and the number of its vertices is the [1, k]-domination number [formula] of G. In this short note we show that the decision problem whether [formula] is an NP-hard problem, even for bipartite graphs. Also, a simple construction of a bipartite graph G of order n satisfying [formula] is given for every integer n ≥ (k + l)(2k + 3).

2

Congruences of Edge-bipartite Graphs with Applications to Grothendieck Group Recognition. [Part 2], Coxeter Type Study

Mróz A.

Fundamenta Informaticae

|

2016

|

Vol. 146, nr 2

145--177

EN

In this two parts article with the same main title we study a problem of Coxeter-Gram spectral analysis of edge-bipartite graphs (bigraphs), a class of signed graphs. We ask for a criterion deciding if a given bigraph Δ is weakly or strongly Gram-congruent with a graph. The problem is inspired by recent works of Simson et al. started in [SIAM J. Discr. Math. 27 (2013), 827-854], and by problems related to integral quadratic forms, bilinear lattices, representation theory of algebras, algebraic methods in graph theory and the isotropy groups of bigraphs. In this Part II we develop general combinatorial techniques, with the use of inflation algorithm discussed in Part I, morsifications and the isotropy group of a bigraph, and we provide a constructive solution of the problem for the class of all positive connected loop-free bigraphs. Moreover, we present an application of our results to Grothendieck group recognition problem: deciding if a given bilinear lattice is the Grothendieck group of some category. Our techniques are tested in a series of experiments for so-called Nakayama bigraphs, illustrating the applications in practice and certain related phenomena. The results show that a computer algebra technique and discrete mathematical computing provide important tools in solving theoretical problems of high complexity.

3

Congruences of Edge-bipartite Graphs with Applications to Grothendieck Group Recognition. [Part 1], Inflation Algorithm Revisited

Mróz A.

Fundamenta Informaticae

|

2016

|

Vol. 146, nr 2

121--144

EN

We study edge-bipartite graphs (bigraphs), a class of signed graphs, by means of the inflation algorithm which relies on performing certain elementary transformations on a given bigraph Δ, or equivalently, on the associated integral quadratic form qΔ: Zn → Z, preserving Gram Z-congruence. The ideas are inspired by classical results of Ovsienko and recent studies of Simson started in [SIAM J. Discr. Math. 27 (2013), 827-854], concerning classifications of integral quadratic and bilinear forms, and their Coxeter spectral analysis. We provide few modifications of the inflation algorithm and new estimations of its complexity for positive and principal loop-free bigraphs. We discuss in a systematic way the behavior and computational aspects of inflation techniques. As one of the consequences we obtain relatively simple proofs of several interesting properties of quadratic forms and their roots, extending known facts. On the other hand, the results are a first step of a solution of a variant of Grothendieck group recognition, a difficult combinatorial problem arising in representation theory of finite dimensional algebras and their derived categories, which we discuss in Part II of this two parts article with the same main title.

4

Periodic Partial Words and Random Bipartite Graphs

Idiatulina L. A., Shur A. M.

Fundamenta Informaticae

|

2014

|

Vol. 132, nr 1

15--31

EN

The interaction property (or the Fine-Wilf property) for periodic partial words is studied. Partial words with two periods are represented by bipartite graphs and the interaction property is related to the edge connectedness property of these graphs. Threshold functions for the edge connectedness of random bipartite graphs and multigraphs are found. As a corollary, the interaction property is described in probabilistic terms.

5

Computer Algebra Technique for Coxeter Spectral Study of Edge-bipartite Graphs and Matrix Morsifications of Dynkin Type An

Felisiak M.

Fundamenta Informaticae

|

2013

|

Vol. 125, nr 1

21--49

EN

By applying computer algebra tools (mainly, Maple and C++), given the Dynkin diagram ∆ = An, with n > 2 vertices and the Euler quadratic form q∆ : Zn → Z, we study the problem of classifying mesh root systems and the mesh geometries of roots of A (see Section 1 for details). The problem reduces to the computation of the Weyl orbits in the set Mor∆ ⊆ Mn(Z) of all matrix modifications A of q∆, i.e., the non-singular matrices A ∈ Mn(Z) such that (i) q∆ (v) = v A vtr, for all v ∈ Zn, and (ii) the Coxeter matrix CoxA := —A A-tr lies in Gl(n, Z). The Weyl group W∆ ⊆ Gl(n, Z) acts on MorA and the determinant det A ∈ Z, the order cA > 2 of CoxA (i.e. the Coxeter number), and the Coxeter polynomial coxA(t) := det(t E — CoxA) ∈ Z[t] are W∆ -invariant. The problem of determining the W∆ -orbits Orb(A) of MorA and the Coxeter polynomials coxA(t), with A e MorA, is studied in the paper and we get its solution for n < 8, and A = [aij] ∈ MorAn, with [aij] | < 1. In this case, we prove that the number of the W∆ - orbits Orb(A) and the number of the Coxeter polynomials coxA(t) equals two or three, and the following three conditions are equivalent: (i) Orb(A) = Orb(A'), (ii) coxA(t) = coxA> (t), (iii) cA det A = cA det A!. We also construct: (a) three pairwise different W∆ -orbits in Mor∆, with pairwise different Coxeter polynomials, if ∆ = A2m-i and m > 3; and (b) two pairwise different W∆ -orbits in Mor∆, with pairwise different Coxeter polynomials, if ∆ = A2m and m > 1.

6

Global offensive k-alliance in bipartite graphs

Chellali M., Volkmann L.

Opuscula Mathematica

|

2012

|

Vol. 32, no. 1

83-89

EN

Let k ≥ 0 be an integer. A set S of vertices of a graph G = (V (G), E(G)) is called a global offensive k-alliance if /N(v) ∩ S/ ≥ /N(v) - S/ + k for every v ∈ V (G) - S, where 0 ≤ k Δ and Δ is the maximum degree of G. The global offensive k-alliance number [formula] is the minimum cardinality of a global offensive k-alliance in G. We show that for every bipartite graph G and every integer k ≥ 2, [formula], where Lk(G) is the set of vertices of degree at most k - 1. Moreover, extremal trees attaining this upper bound are characterized.

7

Analog Circuits Sizing Using the Fixed Point Iteration Algorithm with Transistor Compact Models

Javid F., Iskander R., Durbin F., Louerat M.-M.

International Journal of Microelectronics and Computer Science

|

2012

|

Vol. 3, nr 1

7-14

EN

This paper presents an algorithm, based on the fixed point iteration, to solve for sizes and biases using transistor compact models such as BSIM3v3, BSIM4, PSP and EKV. The proposed algorithm simplifies the implementation of sizing and biasing operators. Sizing and biasing operators were originally proposed in the hierarchical sizing and biasing methodology [1]. They allow to compute transistors sizes and biases based on transistor compact models, while respecting the designer's hypotheses. Computed sizes and biases are accurate, and guarantee the correct electrical behavior as expected by the designer. Sizing and biasing operators interface with a Spice-like simulator, allowing possible use of all available compact models for circuit sizing and biasing over different technologies. A bipartite graph , that contains sizing and biasing operators, is associated to the design view of a circuit, it is the design procedure for the given circuit. To illustrate the effectiveness of the proposed fixed point algorithm, a folded cascode OTA is efficiently sized with a 130nm process, then migrated to a 65nm technology. Both sizing and migration are performed in a few milliseconds.

8

Random graph generator for bipartite networks modeling

Chojnacki Sz., Kłopotek M. A.

Control and Cybernetics

|

2011

|

Vol. 40, no 3

697-714

EN

The purpose of this article is to introduce a new bipartite graph generation algorithm. Bipartite graphs consist of two types of nodes and edges join only nodes of different types. This data structure appears in various applications (e.g. recommender systems or text clustering). Both real-life datasets and formal tools enable us to evaluate only a limited set of properties of the algorithms that are used in such situations. Therefore, artificial datasets are needed to enhance development and testing of the algorithms. Our generator can be used to produce a wide range of synthetic datasets.

9

Cyclability in bipartite graphs

Amar D., Flandrin E., Gancarzewicz G.

Opuscula Mathematica

|

2009

|

Vol. 29, no. 4

345-364

EN

Let G = (X, Y; E) be a balanced 2-connected bipartite graph and S ⊂ V(G). We will say that S is cyclable in G if all vertices of S belong to a common cycle in G. We give sufficient degree conditions in a balanced bipartite graph G and a subset S ⊂ V(G) for the cyclability of the set S.

10

Metoda porównywania drzew filogenetycznych wykorzystująca najlżejsze doskonałe skojarzenie w grafach dwudzielnych

Bogdanowicz D.

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

|

2008

|

T. 15

183-188

PL

Drzewa filogenetyczne przedstawiają historyczne, ewolucyjne związki pokrewieństwa między różnymi gatunkami lub różnymi osobnikami w ramach jednego gatunku. Istnieje wiele metod rekonstruowania drzew filogenetycznych. Wykorzystywanie różnych metod na tym samym zbiorze danych zazwyczaj owocuje powstaniem różnych drzew. Pojawia się zatem pytanie: jak bardzo dwa dane drzewa różnią się od siebie. W niniejszej pracy prezentujemy nową ogólną metodę porównywana drzew filogenetycznych. Metoda opiera się na wykorzystaniu najlżejszego doskonałego skojarzenia w grafach dwudzielnych i przy opisanych założeniach wymaga wielomianowego czasu obliczeń. W pracy omówiono podstawowe własności metryki oraz podano trzy przypadki szczególne. Przedstawiono także wyniki eksperymentów obliczeniowych.

EN

A phylogenetic tree represents historical evolutionary relationship between different species or organisms. There are various methods for reconstructing phylogenetic trees. Applying those techniques usually results in different trees for the same input data. An important problem is to determine how distant two trees reconstructed in such a way are from each other. In this paper, new metrics for comparing phylogenetics trees are suggested. These metrics are based on minimum weight perfect matching in bipartite graphs and can be computed in a polynomial time. We study same properties of these metrics and compare them with methods previously known.

11

O złożoności problemów F-dekompozycji grafów>

Jesse-Józefczyk K.

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

|

2007

|

T. 13

419-426

PL

W pracy tej zostało przedstawionych kilka problemów związanych z F-dekompozycją grafów i jej złożonością obliczeniową. F-dekompozycję będziemy utożsamiać z częściowym dwukolorowaniem wierzchołków grafu. Kolorowanie to musi spełniać kilka warunków, z których najważniejszym jest to, aby krawędzie czerwono-niebieskie tworzyły zbiór rozspajający dany graf oraz wraz z wierzchołkami w tych kolorach nie indukowały pewnych grafów dwudzielnych.

EN

This paper presents selected problems concerning F-decomposition of graphs and its complexity. We identify the F-decomposition with a colouring of vertices of a graph. This colouring must satisfy several conditions and the most important of them is that the red-blue edges must be a cut-set of the given graph and together with the vertices coloured red and blue they cannot induce some bipartite graphs.

12

Bipartite graph approach to coordinating disparate workflows

Biegus Ł., Branki C.

Machine Graphics and Vision

|

2003

|

Vol. 12, No. 1

61-71

EN

This paper presents a way of modelling and executing inter-company workflows that require parallel-synchronised interperability approach. The modellin is carried out using the concepts of coorination dialogue and bipartite graph. Execution requires a kind of messaging service, which can conveniently be implemented with software agents.

13

Wybrane problemy harmonogramowania procesów w oparciu o dwudzielne grafy konfliktowe

Małafiejski M.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2001

|

T. 5, z. 1/2

403-409

PL

W pracy dokonano podsumowania większości znanych wyników dotyczących problemu minimalizacji średniego czasu przepływu zadań w systemie wieloprocesorowych zadań współdzielących zasoby (pliki, procesory, maszyny). Konflikty w dostępie do współdzielonych zasobów modelują tzw. grafy konfliktowe. W szczególności dla zadań, które można podzielić na dwa zbiory (zadania typu I oraz II) tak, że żadne dwa zadania jednego typu nie współdzielą tego samego zasobu, grafy konliktowe są dwudzielne. Konstrukcję optymalnych uszeregowań można równoważnie sprowadzić do konstrukcji pokolorowań grafów konfliktowych realizujących sumę (multi)chromatyczną. Wykorzystując bogaty aparat teorii grafów dla wybranych klas grafów dwudzielnych można skonstruować wielomianowe algorytmy optymalne (drzewa, pełne, regularne), korzystając dodatkowo z technik dowodzenia NP-zupełności można rozstrzygnąć problem złożoności obliczeniowej wybranych problemów decyzyjnych (np. grafy dwudzielne z ograniczonych maksymalnym stopniem). Dodatkowo przedstawione zostały problemy otwarte związane z prezentowaną tematyką, w szczególności problemy złożoności uszeregowania zadań całkowitych (ścieżki, drzewa).

EN

In the paper the author considers the problem of scheduling multiprocessor tasks with resource conflicts modelled by bipartite graphs. Consider the following scenario that exemplifies the problem. Given n jobs executed in a distributed computing environment. Suppose that each job running on different processor requires exclusively a subset of the set of files stored in the network file system. The execution time of each job is multiplicity of the unit execution time. The jobs and the conflicts between them in accesses to the shared files are represented by vertices and edges of the graph, respectively. The associated graph we call a conflicting graph. Based on the graph theory and NP-complete results the author presents polynomial time and NP-complete results. Moreover, the author states some new open questions concerning the problem.