Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 7

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  complexity
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote

An Oriented Version of the 1-2-3 Conjecture

100%
Baudon O., Bensmail J., Sopena É.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 1
141-156
EN
The well-known 1-2-3 Conjecture addressed by Karoński, Luczak and Thomason asks whether the edges of every undirected graph G with no isolated edge can be assigned weights from {1, 2, 3} so that the sum of incident weights at each vertex yields a proper vertex-colouring of G. In this work, we consider a similar problem for oriented graphs. We show that the arcs of every oriented graph −G⃗ can be assigned weights from {1, 2, 3} so that every two adjacent vertices of −G⃗ receive distinct sums of outgoing weights. This result is tight in the sense that some oriented graphs do not admit such an assignment using the weights from {1, 2} only. We finally prove that deciding whether two weights are sufficient for a given oriented graph is an NP-complete problem. These results also hold for product or list versions of this problem.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On 𝓕-independence in graphs

100%
Göring F., Harant J., Rautenbach D., Schiermeyer I.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 2
377-383
EN
Let 𝓕 be a set of graphs and for a graph G let $α_{𝓕}(G)$ and $α*_{𝓕}(G)$ denote the maximum order of an induced subgraph of G which does not contain a graph in 𝓕 as a subgraph and which does not contain a graph in 𝓕 as an induced subgraph, respectively. Lower bounds on $α_{𝓕}(G)$ and $α*_{𝓕}(G)$ are presented.
3
Content available remote

Complexity of weakly null sequences

90%
Alspach D. E., Argyros S.
Instytut Matematyczny Polskiej Akademii Nauk
EN
CONTENTS 0. Introduction.................................................................................................5 1. Preliminaries...............................................................................................6 2. Weakly null sequences and the l¹-index......................................................9 3. Comparison with the l¹-index.....................................................................12 4. Construction of weakly null sequences with large oscillation index............21 5. Reflexive spaces with large oscillation index.............................................33 6. Comparison with the averaging index........................................................37 References....................................................................................................43
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A survey of hereditary properties of graphs

88%
Borowiecki M., Broere I., Frick M., Mihók P., Semanišin G.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 1
5-50
EN
In this paper we survey results and open problems on the structure of additive and hereditary properties of graphs. The important role of vertex partition problems, in particular the existence of uniquely partitionable graphs and reducible properties of graphs in this structure is emphasized. Many related topics, including questions on the complexity of related problems, are investigated.
5
Content available remote

Set membership estimation of parameters and variables in dynamic networks by recursive algorithms with a moving measurement window

88%
Duzinkiewicz K.
International Journal of Applied Mathematics and Computer Science
|
2006
|
tom 16
|
nr 2
209-217
EN
The paper considers a set membership joint estimation of variables and parameters in complex dynamic networks based on parametric uncertain models and limited hard measurements. A recursive estimation algorithm with a moving measurement window is derived that is suitable for on-line network monitoring. The window allows stabilising the classic recursive estimation algorithm and significantly improves estimate tightness. The estimator is validated on a case study regarding a water distribution network. Tight set estimates of unmeasured pipe flows, nodal heads, tank level and pipe resistances are obtained.
6
Content available remote

Emotion learning: Solving a shortest path problem in an arbitrary deterministic environment in linear time with an emotional agent

88%
Etruseva S.
International Journal of Applied Mathematics and Computer Science
|
2008
|
tom 18
|
nr 3
409-421
EN
The paper presents an algorithm which solves the shortest path problem in an arbitrary deterministic environment with n states with an emotional agent in linear time. The algorithm originates from an algorithm which in exponential time solves the same problem, and the agent architecture used for solving the problem is an NN-CAA architecture (neural network crossbar adaptive array). By implementing emotion learning, the linear time algorithm is obtained and the agent architecture is modified. The complexity of the algorithm without operations for initiation in general does not depend on the number of states n, but only on the length of the shortest path. Depending on the position of the goal state, the complexity can be at most O(n). It can be concluded that the choice of the function which evaluates the emotional state of the agent plays a decisive role in solving the problem efficiently. That function should give as detailed information as possible about the consequences of the agent's actions, starting even from the initial state. In this way the function implements properties of human emotions.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Spanning trees with many or few colors in edge-colored graphs

63%
Broersma H., Li X.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 2
259-269
EN
Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, we consider the complexity of finding a spanning tree of G with as many different colors as possible, and of finding one with as few different colors as possible. We show that the first problem is equivalent to finding a common independent set of maximum cardinality in two matroids, implying that there is a polynomial algorithm. We use the minimum dominating set problem to show that the second problem is NP-hard.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.