Wyniki wyszukiwania dla: graph algorithms - MOST Wiedzy

Wyszukiwarka

Wyniki wyszukiwania dla: graph algorithms

Filtry

wszystkich: 315
wybranych: 276

wyczyść wszystkie filtry


Filtry wybranego katalogu

  • Kategoria

  • Rok

  • Opcje

wyczyść Filtry wybranego katalogu niedostępne

Wyniki wyszukiwania dla: graph algorithms

  • Application of genetic algorithms in graph searching problem

    Graph searching is a common approach to solving a problem of capturing a hostile intruder by a group of mobile agents. We assume that this task is performed in environment which we are able to model as a graph G. The question asked is how many agents are needed to capture an arbitrary fast, invisible and smart intruder. This number is called the (edge) search number of G. The strategy which must be performed by agents is called...

  • Multi-agent graph searching and exploration algorithms

    Publikacja

    - Rok 2020

    A team of mobile entities, which we refer to as agents or searchers interchangeably, starting from homebases needs to complete a given task in a graph.The goal is to build a strategy, which allows agents to accomplish their task. We analyze strategies for their effectiveness (e.g., the number of used agents, the total number of performed moves by the agents or the completion time).Currently, the fields of on-line (i.e., agents...

    Pełny tekst do pobrania w portalu

  • An experimental study of distributed algorithms for graph coloring.

    W pracy podano algorytm rozproszonego kolorowania grafówi porównano ze znanym wcześniej algorytmem.

  • Greedy algorithms for backbone graph coloring in KOALA library

    Publikacja

    - Rok 2012

  • Self-stabilizing algorithms for graph coloring with improved performance guarantees

    Publikacja

    W pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm kolorowania grafów oparty na konstrukcji drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm z gwarantowaną wielomianową liczbą ruchów, który dokładnie koloruje grafy dwudzielne.

  • Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines: Complexity and Algorithms

    Publikacja

    - ARTIFICIAL INTELLIGENCE - Rok 2022

    In this paper, the problem of scheduling on parallel machines with a presence of incompatibilities between jobs is considered. The incompatibility relation can be modeled as a complete multipartite graph in which each edge denotes a pair of jobs that cannot be scheduled on the same machine. The paper provides several results concerning schedules, optimal or approximate with respect to the two most popular criteria of optimality:...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Application of Graph Theory Algorithms in Non-disjoint Functional Decomposition of Specific Boolean Functions

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Reconfiguring Minimum Dominating Sets in Trees

    Publikacja

    We provide tight bounds on the diameter of γ-graphs, which are reconfiguration graphs of the minimum dominating sets of a graph G. In particular, we prove that for any tree T of order n ≥ 3, the diameter of its γ-graph is at most n/2 in the single vertex replacement adjacency model, whereas in the slide adjacency model, it is at most 2(n − 1)/3. Our proof is constructive, leading to a simple linear-time algorithm for determining...

    Pełny tekst do pobrania w portalu

  • Constructing a map of an anonymous graph: applications of universal sequences

    Publikacja

    - LECTURE NOTES IN COMPUTER SCIENCE - Rok 2010

    We study the problem of mapping an unknown environmentrepresented as an unlabelled undirected graph. A robot (or automaton)starting at a single vertex of the graph G has to traverse the graph and return to its starting point building a map of the graph in the process. We are interested in the cost of achieving this task (whenever possible) in terms of the number of edge traversal made by the robot. Another optimization criteria...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • On zero-error codes produced by greedy algorithms

    We present two greedy algorithms that determine zero-error codes and lower bounds on the zero-error capacity. These algorithms have many advantages, e.g., they do not store a whole product graph in a computer memory and they use the so-called distributions in all dimensions to get better approximations of the zero-error capacity. We also show an additional application of our algorithms.

    Pełny tekst do pobrania w portalu

  • Product Graph Invariants with Applications in the Theory of Information

    Publikacja

    - Rok 2012

    There are a large number of graph invariants. In the paper, we consider some of them, e.g. the independence and chromatic numbers. It is well know that we cannot efficiently calculate these numbers for arbitrary graphs. In the paper we present relations between these invariants and concepts from the theory of information. Concepts such as source coding and transmission over a noisy channel with zero probability of error are modeled...

  • Parallel tabu search for graph coloring problem

    Publikacja

    Tabu search is a simple, yet powerful meta-heuristic based on local search that has been often used to solve combinatorial optimization problems like the graph coloring problem. This paper presents current taxonomy of patallel tabu search algorithms and compares three parallelization techniques applied to Tabucol, a sequential TS algorithm for graph coloring. The experimental results are based on graphs available from the DIMACS...

  • Graph security testing

    Set S ⊂ V is called secure set iff ∀ X ⊂ S | N [ X ] ∩ S | ≥ | N ( X ) \ S | [3]. That means that every subset of a secure set has at least as many friends (neighbour vertices in S) as enemies (neighbour vertices outside S) and will be defended in case of attack. Problem of determining if given set is secure is co −NP -complete, there is no efficient algorithm solving it [3]. Property testers are algorithms that distinguish inputs...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Extending Service Selection Algorithms with Interoperability Analysis

    Application development by integration of existing, atomic services reduces development cost and time by extensive reuse of service components. In Service Oriented Architecture, there exist alternative versions of services supplying the same functionality but differing in Quality of Service (QoS) attributes, which enables developers to select services with optimal QoS. Existing algorithms of service selection focus on the formal...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Comparison and Analysis of Service Selection Algorithms

    Publikacja

    - Rok 2013

    In Service Oriented Architecture, applications are developed by integration of existing services in order to reduce development cost and time. The approach, however, requires algorithms that select appropriate services out of available, alternative ones. The selection process may consider both optimalization requirements, such as maximalization of performance, and constraint requirements, such minimal security or maximum development...

  • Interoperability Constraints in Service Selection Algorithms

    Publikacja

    - Rok 2012

    In Service Oriented Architecture, composite applications are developed by integration of existing, atomic services that may be available in alternative versions realizing the same functionality but having different Quality of Service (QoS) attributes. The development process requires effective service selection algorithms that balance profits and constraints of QoS attributes. Additionally, services operate in a heterogeneous environment,...

  • Approximation algorithms for job scheduling with block-type conflict graphs

    Publikacja

    - COMPUTERS & OPERATIONS RESEARCH - Rok 2024

    The problem of scheduling jobs on parallel machines (identical, uniform, or unrelated), under incompatibility relation modeled as a block graph, under the makespan optimality criterion, is considered in this paper. No two jobs that are in the relation (equivalently in the same block) may be scheduled on the same machine in this model. The presented model stems from a well-established line of research combining scheduling theory...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • GreedyMAX-type Algorithms for the Maximum Independent Set Problem

    Publikacja

    A maximum independent set problem for a simple graph G = (V,E) is to find the largest subset of pairwise nonadjacent vertices. The problem is known to be NP-hard and it is also hard to approximate. Within this article we introduce a non-negative integer valued functionp defined on the vertex set V(G) and called a potential function of agraph G, while P(G) = max{vinV(G)| p(v)} is called a potential of G. For any graph P(G) <= D(G),...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Comparison of reproduction strategies in genetic algorithm approach to graph searching

    genetic algorithms (ga) are a well-known tool used to obtain approximate solutions to optimization problems. successful application of genetic algorithm in solving given problem is largely dependant on selecting appropriate genetic operators. selection, mutation and crossover techniques play a fundamental role in both time needed to obtain results and their accuracy. in this paper we focus on applying genetic algorithms in calculating...

  • A space-efficient algorithm for computing the minimum cycle mean in a directed graph

    An algorithm is introduced for computing the minimum cycle mean in a strongly connected directed graph with n vertices and m arcs that requires O(n) working space. This is a considerable improvement for sparse graphs in comparison to the classical algorithms that require O(n^2) working space. The time complexity of the algorithm is still O(nm). An implementation in C++ is made publicly available at http://www.pawelpilarczyk.com/cymealg/.

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines

    Publikacja

    In this paper we consider a problem of job scheduling on parallel machines with a presence of incompatibilities between jobs. The incompatibility relation can be modeled as a complete multipartite graph in which each edge denotes a pair of jobs that cannot be scheduled on the same machine. Our research stems from the works of Bodlaender, Jansen, and Woeginger (1994) and Bodlaender and Jansen (1993). In particular, we pursue the...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Equitable coloring of corona multiproducts of graphs

    Publikacja

    - Discussiones Mathematicae Graph Theory - Rok 2017

    We give some results regarding the equitable chromatic number for l-corona product of two graphs: G and H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G.

    Pełny tekst do pobrania w portalu

  • Pawlak's flow graph extensions for video surveillance systems

    Publikacja

    The idea of the Pawlak's flow graphs is applicable to many problems in various fields related to decision algorithms or data mining. The flow graphs can be used also in the video surveillance systems. Especially in distributed multi-camera systems which are problematic to be handled by human operators because of their limited perception. In such systems automated video analysis needs to be implemented. Important part of this analysis...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Computer experiments with a parallel clonal selection algorithm for the graph coloring problem

    Publikacja

    Artificial immune systems (AIS) are algorithms that are based on the structure and mechanisms of the vertebrate immune system. Clonal selection is a process that allows lymphocytes to launch a quick response to known pathogens and to adapt to new, previously unencountered ones. This paper presents a parallel island model algorithm based on the clonal selection principles for solving the Graph Coloring Problem. The performance of...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Algorithms for testing security in graphs

    In this paper we propose new algorithmic methods giving with the high probability the correct answer to the decision problem of security in graphs. For a given graph G and a subset S of a vertex set of G we have to decide whether S is secure, i.e. every subset X of S fulfils the condition: |N[X] \cap S| >= |N[X] \ S|, where N[X] is a closed neighbourhood of X in graph G. We constructed a polynomial time property pseudotester based...

    Pełny tekst do pobrania w portalu

  • Comparison of selected algorithms for scheduling workflow applications with dynamically changing service availability

    This paper compares the quality and execution times of several algorithms for scheduling service based workflow applications with changeable service availability and parameters. A workflow is defined as an acyclic directed graph with nodes corresponding to tasks and edges to dependencies between tasks. For each task, one out of several available services needs to be chosen and scheduled to minimize the workflow execution time and...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • The Backbone Coloring Problem for Small Graphs

    In this paper we investigate the values of the backbone chromatic number, derived from a mathematical model for the problem of minimization of bandwidth in radio networks, for small connected graphs and connected backbones (up to 7 vertices). We study the relationship of this parameter with the structure of the graph and compare the results with the solutions obtained using the classical graph coloring algorithms (LF, IS), modified...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • An Alternative Proof of a Lower Bound on the 2-Domination Number of a Tree

    A 2-dominating set of a graph G is a set D of vertices of G such that every vertex not in D has a at least two neighbors in D. The 2-domination number of a graph G, denoted by gamma_2(G), is the minimum cardinality of a 2-dominating set of G. Fink and Jacobson [n-domination in graphs, Graph theory with applications to algorithms and computer science, Wiley, New York, 1985, 283-300] established the following lower bound on the 2-domination...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • The Potential of Greed for Independence

    Publikacja

    - JOURNAL OF GRAPH THEORY - Rok 2012

    The well-known lower bound on the independence number of a graph due to Caro and Wei can be established as a performance guarantee of two natural and simple greedy algorithms or of a simple randomized algorithm. We study possible generalizations and improvements of these approaches using vertex weights and discuss conditions on so-called potential functions p(G) : V(G) -> N_0 defined on the vertex set of a graph G for which suitably...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • On-line ranking of split graphs

    A vertex ranking of a graph G is an assignment of positive integers (colors) to the vertices of G such that each path connecting two vertices of the same color contains a vertex of a higher color. Our main goal is to find a vertex ranking using as few colors as possible. Considering on-line algorithms for vertex ranking of split graphs, we prove that the worst case ratio of the number of colors used by any on-line ranking algorithm...

    Pełny tekst do pobrania w portalu

  • A NOTE ON ON-LINE RAMSEY NUMBERS FOR QUADRILATERALS

    Publikacja

    - Opuscula Mathematica - Rok 2014

    We consider on-line Ramsey numbers defined by a game played between two players, Builder and Painter. In each round Builder draws an the edge and Painter colors it either red or blue, as it appears. Builder’s goal is to force Painter to create a monochromatic copy of a fixed graph H in as few rounds as possible. The minimum number of rounds (assuming both players play perfectly) is the on-line Ramsey number \widetilde{r}(H) of...

    Pełny tekst do pobrania w portalu

  • Graph Neural Networks and Structural Information on Ionic Liquids: A Cheminformatics Study on Molecular Physicochemical Property Prediction

    Ionic liquids (ILs) provide a promising solution in many industrial applications, such as solvents, absorbents, electrolytes, catalysts, lubricants, and many others. However, due to the enormous variety of their structures, uncovering or designing those with optimal attributes requires expensive and exhaustive simulations and experiments. For these reasons, searching for an efficient theoretical tool for finding the relationship...

    Pełny tekst do pobrania w portalu

  • On-line P-coloring of graphs

    For a given induced hereditary property P, a P-coloring of a graph G is an assignment of one color to each vertex such that the subgraphs induced by each of the color classes have property P. We consider the effectiveness of on-line P-coloring algorithms and give the generalizations and extensions of selected results known for on-line proper coloring algorithms. We prove a linear lower bound for the performance guarantee function...

    Pełny tekst do pobrania w portalu

  • Isolation Number versus Domination Number of Trees

    Publikacja
    • M. Lemańska
    • M. J. Souto-Salorio
    • A. Dapena
    • F. Vazquez-Araujo

    - Mathematics - Rok 2021

    If G=(VG,EG) is a graph of order n, we call S⊆VG an isolating set if the graph induced by VG−NG[S] contains no edges. The minimum cardinality of an isolating set of G is called the isolation number of G, and it is denoted by ι(G). It is known that ι(G)≤n3 and the bound is sharp. A subset S⊆VG is called dominating in G if NG[S]=VG. The minimum cardinality of a dominating set of G is the domination number, and it is denoted by γ(G)....

    Pełny tekst do pobrania w portalu

  • Generating optimal paths in dynamic environments using RiverFormation Dynamics algorithm

    The paper presents a comparison of four optimisation algorithms implemented for the purpose of finding the shortest path in static and dynamic environments with obstacles. Two classical graph algorithms –the Dijkstra complete algorithm and A* heuristic algorithm – were compared with metaheuristic River Formation Dynamics swarm algorithm and its newly introduced modified version. Moreover, another swarm algorithm has been compared...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Exploiting multi-interface networks: Connectivity and Cheapest Paths

    Publikacja

    - WIRELESS NETWORKS - Rok 2010

    Let G = (V,E) be a graph which models a set of wireless devices (nodes V) that can communicate by means of multiple radio interfaces, according to proximity and common interfaces (edges E). The problem of switching on (activating) the minimum cost set of interfaces at the nodes in order to guarantee the coverage of G was recently studied. A connection is covered (activated) when the endpoints of the corresponding edge share at...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Global defensive sets in graphs

    In the paper we study a new problem of finding a minimum global defensive set in a graph which is a generalization of the global alliance problem. For a given graph G and a subset S of a vertex set of G, we define for every subset X of S the predicate SEC ( X ) = true if and only if | N [ X ] ∩ S | ≥ | N [ X ] \ S | holds, where N [ X ] is a closed neighbourhood of X in graph G. A set S is a defensive alliance if and only if for...

    Pełny tekst do pobrania w portalu

  • Global edge alliances in graphs

    In the paper we introduce and study a new problem of finding a minimum global edge alliance in a graph which is related to the global defensive alliance (Haynes et al., 2013; Hedetniemi, 2004) and the global defensive set (Lewoń et al., 2016). We proved the NP-completeness of the global edge alliance problem for subcubic graphs and we constructed polynomial time algorithms for trees. We found the exact values of the size of the...

    Pełny tekst do pobrania w portalu

  • Path-based methods on categorical structures for conceptual representation of wikipedia articles

    Machine learning algorithms applied to text categorization mostly employ the Bag of Words (BoW) representation to describe the content of the documents. This method has been successfully used in many applications, but it is known to have several limitations. One way of improving text representation is usage of Wikipedia as the lexical knowledge base – an approach that has already shown promising results in many research studies....

    Pełny tekst do pobrania w portalu

  • Stereo vision with Equal Baseline Multiple Camera Set (EBMCS) for obtaining depth maps of plants

    This paper presents a method of improving the estimation of distances between an autonomous harvesting robot and plants with ripe fruits by using the vision system based on five cameras. The system is called Equal Baseline Multiple Camera Set (EBMCS). EBMCS has some features of a camera matrix and a camera array. EBMCS is regarded as a set of stereo cameras for estimating distances by obtaining disparity maps and depth maps. This...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Rearrangeability in multicast Clos networks is NP-complete

    Publikacja

    Przestrajalność w polach Closa z połączeniami jeden do jeden jest problemem wielomianowym. W pracy pokazano, że w polach z połączeniami jeden do wiele problem ten jest NP zupełny.Three-stage elos networks are commutation networks with circuit switching. So far, graph theory has been very useful tool for solving issues related to these networks with unicast connections. This is so because if elos network is represented as a bipartite...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Eventual Convergence of the Reputation-Based Algorithm in IoT Sensor Networks

    Publikacja

    - SENSORS - Rok 2021

    Uncertainty in dense heterogeneous IoT sensor networks can be decreased by applying reputation-inspired algorithms, such as the EWMA (Exponentially Weighted Moving Average) algorithm, which is widely used in social networks. Despite its popularity, the eventual convergence of this algorithm for the purpose of IoT networks has not been widely studied, and results of simulations are often taken in lieu of the more rigorous proof....

    Pełny tekst do pobrania w portalu

  • Comparing Phylogenetic Trees by Matching Nodes Using the Transfer Distance Between Partitions

    Publikacja

    - JOURNAL OF COMPUTATIONAL BIOLOGY - Rok 2017

    Ability to quantify dissimilarity of different phylogenetic trees describing the relationship between the same group of taxa is required in various types of phylogenetic studies. For example, such metrics are used to assess the quality of phylogeny construction methods, to define optimization criteria in supertree building algorithms, or to find horizontal gene transfer (HGT) events. Among the set of metrics described so far in...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • The computational complexity of the backbone coloring problem for planar graphs with connected backbones

    In the paper we study the computational complexity of the backbone coloring problem for planar graphs with connected backbones. For every possible value of integer parameters λ≥2 and k≥1 we show that the following problem: Instance: A simple planar graph GG, its connected spanning subgraph (backbone) HH. Question: Is there a λ-backbone coloring c of G with backbone H such that maxc(V(G))≤k? is either NP-complete or polynomially...

    Pełny tekst do pobrania w portalu

  • Scheduling of compatible jobs on parallel machines

    Publikacja

    - Rok 2021

    The dissertation discusses the problems of scheduling compatible jobs on parallel machines. Some jobs are incompatible, which is modeled as a binary relation on the set of jobs; the relation is often modeled by an incompatibility graph. We consider two models of machines. The first model, more emphasized in the thesis, is a classical model of scheduling, where each machine does one job at time. The second one is a model of p-batching...

  • Planning optimised multi-tasking operations under the capability for parallel machining

    The advent of advanced multi-tasking machines (MTMs) in the metalworking industry has provided the opportunity for more efficient parallel machining as compared to traditional sequential processing. It entailed the need for developing appropriate reasoning schemes for efficient process planning to take advantage of machining capabilities inherent in these machines. This paper addresses an adequate methodical approach for a non-linear...

    Pełny tekst do pobrania w portalu

  • Global defensive secure structures

    Publikacja

    Let S ⊂ V (G) for a given simple non-empty graph G. We define for any nonempty subset X of S the predicate SECG,S(X) = true iff |NG[X]∩S| ≥ |NG[X]\S|. Let H be a non-empty family of graphs such that for each vertex v ∈ V (G) there is a subgraph H of G containing v and isomorphic to a member of H. We introduce the concept of H-alliance extending the concept of global defensive secure structures. By an H-alliance in a graph G we...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Towards More Realistic Probabilistic Models for Data Structures: The External Path Length in Tries under the Markov Model

    Publikacja

    - Rok 2013

    Tries are among the most versatile and widely used data structures on words. They are pertinent to the (internal) structure of (stored) words and several splitting procedures used in diverse contexts ranging from document taxonomy to IP addresses lookup, from data compression (i.e., Lempel- Ziv'77 scheme) to dynamic hashing, from partial-match queries to speech recognition, from leader election algorithms to distributed hashing...

  • KernelHive: a new workflow-based framework for multilevel high performance computing using clusters and workstations with CPUs and GPUs

    The paper presents a new open-source framework called KernelHive for multilevel parallelization of computations among various clusters, cluster nodes, and finally, among both CPUs and GPUs for a particular application. An application is modeled as an acyclic directed graph with a possibility to run nodes in parallel and automatic expansion of nodes (called node unrolling) depending on the number of computation units available....

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Total Completion Time Minimization for Scheduling with Incompatibility Cliques

    Publikacja

    - Rok 2021

    This paper considers parallel machine scheduling with incompatibilities between jobs. The jobs form a graph equivalent to a collection of disjoint cliques. No two jobs in a clique are allowed to be assigned to the same machine. Scheduling with incompatibilities between jobs represents a well-established line of research in scheduling theory and the case of disjoint cliques has received increasing attention in recent...

    Pełny tekst do pobrania w serwisie zewnętrznym