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-11 z 11
    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ł:
    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ł:
    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ł:
    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ł
      Wyświetlanie 1-11 z 11

      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