Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "graph algorithms" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 23
Tytuł:
Factoring directed graphs with respect to the cardinal product in polynomial time
Autorzy:
Imrich, Wilfried
Klöckl, Werner
Powiązania:
https://bibliotekanauki.pl/articles/743472.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
directed graphs
cardinal product
graph algorithms
Opis:
By a result of McKenzie [4] finite directed graphs that satisfy certain connectivity and thinness conditions have the unique prime factorization property with respect to the cardinal product. We show that this property still holds under weaker connectivity and stronger thinness conditions. Furthermore, for such graphs the factorization can be determined in polynomial time.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 3; 593-601
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Factoring directed graphs with respect to the cardinal product in polynomial time II
Autorzy:
Imrich, Wilfried
Klöckl, Werner
Powiązania:
https://bibliotekanauki.pl/articles/744038.pdf
Data publikacji:
2010
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
directed graphs
cardinal product
graph algorithms
Opis:
By a result of McKenzie [7] all finite directed graphs that satisfy certain connectivity conditions have unique prime factorizations with respect to the cardinal product. McKenzie does not provide an algorithm, and even up to now no polynomial algorithm that factors all graphs satisfying McKenzie's conditions is known. Only partial results [1,3,5] have been published, all of which depend on certain thinness conditions of the graphs to be factored.
In this paper we weaken the thinness conditions and thus significantly extend the class of graphs for which the prime factorization can be found in polynomial time.
Źródło:
Discussiones Mathematicae Graph Theory; 2010, 30, 3; 461-474
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Stable sets for $(P₆,K_{2,3})$-free graphs
Autorzy:
Mosca, Raffaele
Powiązania:
https://bibliotekanauki.pl/articles/743743.pdf
Data publikacji:
2012
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph algorithms
stable sets
P₆-free graphs
Opis:
The Maximum Stable Set (MS) problem is a well known NP-hard problem. However different graph classes for which MS can be efficiently solved have been detected and the augmenting graph technique seems to be a fruitful tool to this aim. In this paper we apply a recent characterization of minimal augmenting graphs [22] to prove that MS can be solved for $(P₆,K_{2,3})$-free graphs in polynomial time, extending some known results.
Źródło:
Discussiones Mathematicae Graph Theory; 2012, 32, 3; 387-401
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Innovative Method of the Evaluation of Multicriterial Multicast Routing Algorithms
Autorzy:
Stachowiak, K.
Zwierzykowski, P.
Powiązania:
https://bibliotekanauki.pl/articles/307838.pdf
Data publikacji:
2013
Wydawca:
Instytut Łączności - Państwowy Instytut Badawczy
Tematy:
evaluation
graph algorithms
multicast
QoS
resource drainage
routing
Opis:
Theoretical considerations of the multicast Quality of Service (QoS) routing have been a rapidly developing and dynamic research area for years. Several algorithms derived from different approaches have been proposed, while the pool of valid solutions to the problem is steadily growing. When new solutions are compared with their predecessors, as much information as possible about their characteristics and differences is needed. Both the graph theory and the optimization theory provide robust and objective means of comparing not only algorithms, but also the results they produce. However, any possible extension to the comparison methods is vital and can bring interesting new information that would eventually lead to innovative conclusions. This article presents a method, derived from practice and experience, that simulates the drainage of resources accumulated by consecutive communication allocations. The nature of this comparison is an extension to the classical measurement of the success ratio and this creates a context of the continuous measure of a success rather than a simple binary value. In this article such a method with regard to algorithms optimizing multicast problems for more than two criteria is used for the first time and leads to an interesting conclusion about the influence of the number of the criteria on the result.
Źródło:
Journal of Telecommunications and Information Technology; 2013, 1; 49-55
1509-4553
1899-8852
Pojawia się w:
Journal of Telecommunications and Information Technology
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Solving Markov decision processes by d-graph algorithms
Autorzy:
Kátai, Z.
Powiązania:
https://bibliotekanauki.pl/articles/205688.pdf
Data publikacji:
2012
Wydawca:
Polska Akademia Nauk. Instytut Badań Systemowych PAN
Tematy:
Markov decision processes
dynamic programming
graph representation
graph algorithms
optimization problems
Opis:
Markov decision processes (MDPs) provide a mathematical model for sequential decisionmaking (sMDP/dMDP: stochastic/ deterministic MDP). We introduce the concept of generalized dMDP (g-dMDP) where each action may result in more than one next (parallel or clone) state. The common tools to represent dMDPs are digraphs, but these are inadequate for sMDPs and g-dMDPs. We introduce d-graphs as general tools to represent all the above mentioned processes (stationary versions). We also present a combined d-graph algorithm that implements dynamic programming strategies to find optimal policies for the finite/infinite horizon versions of these Markov processes. (The preliminary version of this paper was presented at the Conference MACRo 2011.)
Źródło:
Control and Cybernetics; 2012, 41, 3; 577-593
0324-8569
Pojawia się w:
Control and Cybernetics
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A genetic algorithm for the maximum 2-packing set problem
Autorzy:
Trejo-Sánchez, Joel Antonio
Fajardo-Delgado, Daniel
Gutierrez-Garcia, J. Octavio
Powiązania:
https://bibliotekanauki.pl/articles/330154.pdf
Data publikacji:
2020
Wydawca:
Uniwersytet Zielonogórski. Oficyna Wydawnicza
Tematy:
maximum 2-packing set
genetic algorithms
graph algorithms
algorytm genetyczny
algorytm grafowy
Opis:
Given an undirected connected graph G = (V, E), a subset of vertices S is a maximum 2-packing set if the number of edges in the shortest path between any pair of vertices in S is at least 3 and S has the maximum cardinality. In this paper, we present a genetic algorithm for the maximum 2-packing set problem on arbitrary graphs, which is an NP-hard problem. To the best of our knowledge, this work is a pioneering effort to tackle this problem for arbitrary graphs. For comparison, we extended and outperformed a well-known genetic algorithm originally designed for the maximum independent set problem. We also compared our genetic algorithm with a polynomial-time one for the maximum 2-packing set problem on cactus graphs. Empirical results show that our genetic algorithm is capable of finding 2-packing sets with a cardinality relatively close (or equal) to that of the maximum 2-packing sets. Moreover, the cardinality of the 2-packing sets found by our genetic algorithm increases linearly with the number of vertices and with a larger population and a larger number of generations. Furthermore, we provide a theoretical proof demonstrating that our genetic algorithm increases the fitness for each candidate solution when certain conditions are met.
Źródło:
International Journal of Applied Mathematics and Computer Science; 2020, 30, 1; 173-184
1641-876X
2083-8492
Pojawia się w:
International Journal of Applied Mathematics and Computer Science
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Dynamic flows with supply and demand
Autorzy:
Ciurea, E.
Powiązania:
https://bibliotekanauki.pl/articles/205598.pdf
Data publikacji:
2000
Wydawca:
Polska Akademia Nauk. Instytut Badań Systemowych PAN
Tematy:
algorytm grafowy
przepływ dynamiczny
sieć
dynamic flows
graph algorithms
networks
Opis:
We are given a network G = (N, A, h, c) with node set N, arc set A, time function h, capacity function c, and P the set of periods, s the source and s' the sink of the network G. Associated with s, there is a non-negative real number q(t) called the supply of source s at time t, and with s' - a nonnegative real number q'(t) called the demand of sink s' at time t, t [belongs to] P. The objective is to determine the existence of a dynamic flow in G for p periods, so that the demands at sink s' can be fulfilled from the supplies at the source s. A numerical example is presented.
Źródło:
Control and Cybernetics; 2000, 29, 4; 895-903
0324-8569
Pojawia się w:
Control and Cybernetics
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Colouring graphs with prescribed induced cycle lengths
Autorzy:
Randerath, Bert
Schiermeyer, Ingo
Powiązania:
https://bibliotekanauki.pl/articles/743498.pdf
Data publikacji:
2001
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
colouring
chromatic number
induced subgraphs
graph algorithms
χ-binding function
Opis:
In this paper we study the chromatic number of graphs with two prescribed induced cycle lengths. It is due to Sumner that triangle-free and P₅-free or triangle-free, P₆-free and C₆-free graphs are 3-colourable. A canonical extension of these graph classes is $^I(4,5)$, the class of all graphs whose induced cycle lengths are 4 or 5. Our main result states that all graphs of $^I(4,5)$ are 3-colourable. Moreover, we present polynomial time algorithms to 3-colour all triangle-free graphs G of this kind, i.e., we have polynomial time algorithms to 3-colour every $G ∈ ^I(n₁,n₂)$ with n₁,n₂ ≥ 4 (see Table 1). Furthermore, we consider the related problem of finding a χ-binding function for the class $^I(n₁,n₂)$. Here we obtain the surprising result that there exists no linear χ-binding function for $^I(3,4)$.
Źródło:
Discussiones Mathematicae Graph Theory; 2001, 21, 2; 267-281
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A simple linear algorithm for the connected domination problem in circular-arc graphs
Autorzy:
Hung, Ruo-Wei
Chang, Maw-Shang
Powiązania:
https://bibliotekanauki.pl/articles/744451.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph algorithms
circular-arc graphs
connected dominating set
shortest path
Opis:
A connected dominating set of a graph G = (V,E) is a subset of vertices CD ⊆ V such that every vertex not in CD is adjacent to at least one vertex in CD, and the subgraph induced by CD is connected. We show that, given an arc family F with endpoints sorted, a minimum-cardinality connected dominating set of the circular-arc graph constructed from F can be computed in O(|F|) time.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 1; 137-145
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Optimal edge ranking of complete bipartite graphs in polynomial time
Autorzy:
Hung, Ruo-Wei
Powiązania:
https://bibliotekanauki.pl/articles/743901.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph algorithms
edge ranking
vertex ranking
edge-separator tree
complete bipartite graphs
Opis:
An edge ranking of a graph is a labeling of edges using positive integers such that all paths connecting two edges with the same label visit an intermediate edge with a higher label. An edge ranking of a graph is optimal if the number of labels used is minimum among all edge rankings. As the problem of finding optimal edge rankings for general graphs is NP-hard [12], it is interesting to concentrate on special classes of graphs and find optimal edge rankings for them efficiently. Apart from trees and complete graphs, little has been known about special classes of graphs for which the problem can be solved in polynomial time. In this paper, we present a polynomial-time algorithm to find an optimal edge ranking for a complete bipartite graph by using the dynamic programming strategy.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 1; 149-159
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Experimental structure of discourse: mapping the discourse formations of Bauhaus ideals
Autorzy:
Lam, Ka-man
Gorle, Jyotsna
Wilde, Michael
Saad, Patrick
Powiązania:
https://bibliotekanauki.pl/articles/1403665.pdf
Data publikacji:
2020
Wydawca:
Politechnika Białostocka. Oficyna Wydawnicza Politechniki Białostockiej
Tematy:
epistemology
digital humanities
graph algorithms
spatial interface
map-territory relation
software studies
media architecture
Opis:
In the relativistic world of the 21st century, if the Bauhaus would still be upheld as doctrine, we must face the truth: it can hardly be considered a provocation. Rather, we most often find ourselves caught between contradictory wishes to preserve an intact past and to make sense of a resolute avant-gardism. This paper proposes that the Bauhaus, as a discursive knowledge body, be structuralistically analyzed with Foucauldian Discourse Analysis. Our claim is substantiated by: first, that a F oucaultian concept of discourse offers an alternative to the practice of history and theory; second, that the publication of Bauhaus reveals a discursive structure in a F oucaultian sense; third, that discourse-analysis-search-engine can perform the analysis on the Bauhaus corpus, contributing to emergent epistemological positions; fourth, that this revealed structure of discourse could be mapped and re-materialized to invite interferences on today’s territory of Bauhaus Discourse. The research and development process in the accompanying project “Bauhaus Orbits – scenographic apparatus for discourse analysis” (bauhausorbits.de) will be discussed.
Źródło:
Architecturae et Artibus; 2020, 12, 1; 15-28
2080-9638
Pojawia się w:
Architecturae et Artibus
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Analysis of Graph Searching Algorithms for Route Planning in Inland Navigation
Autorzy:
Kazimierski, W.
Sawczak, A.
Wawrzyniak, N.
Powiązania:
https://bibliotekanauki.pl/articles/117106.pdf
Data publikacji:
2015
Wydawca:
Uniwersytet Morski w Gdyni. Wydział Nawigacyjny
Tematy:
Inland Navigation
route planning
Graph Searching Algorithms
Inland Waters
Nautical Spatial Data
Raster Data
vector data
Dijkstra’s Algorithm
Opis:
Route planning is one of the core functionalities of modern navigational systems also in inland waters. There is a possibility of at least partial automation of this process with the use of graph searching algorithms. Main problem here is to create a graph based on nautical spatial data. The paper presents research on examining dif-ferent graph searching methods for inland waters. The concept of using combined approach for vector and ras-ter data is given, followed by research results for raster data.
Źródło:
TransNav : International Journal on Marine Navigation and Safety of Sea Transportation; 2015, 9, 2; 281-286
2083-6473
2083-6481
Pojawia się w:
TransNav : International Journal on Marine Navigation and Safety of Sea Transportation
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Evolutionary approach to obtain graph covering by densely connected subgraphs
Autorzy:
Stańczak, J.
Potrzebowski, H.
Sęp, K.
Powiązania:
https://bibliotekanauki.pl/articles/206170.pdf
Data publikacji:
2011
Wydawca:
Polska Akademia Nauk. Instytut Badań Systemowych PAN
Tematy:
graph
clique
graph clustering
evolutionary algorithms
Opis:
This article describes two evolutionary methods for dividing a graph into densely connected structures. The first method deals with the clustering problem, where the element order plays an important role. This formulation is very useful for a wide range of Decision Support System (DSS) applications. The proposed clustering method consists of two stages. The first is the stage of data matrix reorganization, using a specialized evolutionary algorithm. The second stage is the final clustering step and is performed using a simple clustering method (SCM). The second described method deals with a completely new partitioning algorithm, based on the subgraph structure we call α-clique. The α-clique is a generalization of the clique concept with the introduction of parameter α, which imposes for all vertices of the subgraph the minimal percentage (α*100%) of vertices of this subgraph that must be connected with vertices of this α-clique. Traditional clique is an instance of α-clique with α = 1. Application of this parameter makes it possible to control the degree (or strength) of connections among vertices (nodes) of this subgraph structure. The evolutionary approach is proposed as a method that enables finding separate α-cliques that cover the set of graph vertices.
Źródło:
Control and Cybernetics; 2011, 40, 3; 849-875
0324-8569
Pojawia się w:
Control and Cybernetics
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Graph colorings with local constraints - a survey
Autorzy:
Tuza, Zsolt
Powiązania:
https://bibliotekanauki.pl/articles/972031.pdf
Data publikacji:
1997
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
graph coloring
list coloring
choice number
precoloring extension
complexity of algorithms
chromatic number
Opis:
We survey the literature on those variants of the chromatic number problem where not only a proper coloring has to be found (i.e., adjacent vertices must not receive the same color) but some further local restrictions are imposed on the color assignment. Mostly, the list colorings and the precoloring extensions are considered.
In one of the most general formulations, a graph G = (V,E), sets L(v) of admissible colors, and natural numbers $c_v$ for the vertices v ∈ V are given, and the question is whether there can be chosen a subset C(v) ⊆ L(v) of cardinality $c_v$ for each vertex in such a way that the sets C(v),C(v') are disjoint for each pair v,v' of adjacent vertices. The particular case of constant |L(v)| with $c_v$ = 1 for all v ∈ V leads to the concept of choice number, a graph parameter showing unexpectedly different behavior compared to the chromatic number, despite these two invariants have nearly the same value for almost all graphs.
To illustrate typical techniques, some of the proofs are sketched.
Źródło:
Discussiones Mathematicae Graph Theory; 1997, 17, 2; 161-228
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Analysis of the efficiency of graph coloring algorithms
Autorzy:
Kubale, Marek
Powiązania:
https://bibliotekanauki.pl/articles/748571.pdf
Data publikacji:
1982
Wydawca:
Polskie Towarzystwo Matematyczne
Tematy:
Computational complexity and efficiency of algorithms
Coloring of graphs and hypergraphs
Graph theory
Opis:
.
This paper discusses the computational efficiency and the number of colors used by the following algorithms for coloring vertices of graphs: sequential coloring and sequential coloring with interchange algorithms for a largest-first and a smallest-last orderings of vertices, the coloring-pairs algorithm, and the approximately maximum independent set algorithm. Each algorithm is supplied with a Pascal-like program, time complexity in terms of the size of a graph, and worst-case behaviour. In conclusion, some computational results are included with support the estimations and suggest the sequential coloring with interchange algorithm for a largest-first vertex ordering as a method which uses the least number of colors for uniformly distributed random graphs.
Źródło:
Mathematica Applicanda; 1982, 10, 19
1730-2668
2299-4009
Pojawia się w:
Mathematica Applicanda
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 23

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies