Wyszukiwarka
Filtry
wszystkich: 530
wybranych: 487
Wyniki wyszukiwania dla: query complexity
-
The beauty of architectural complexity
Publikacja -
Parallel query processing and edge ranking of graphs
PublikacjaArtykuł poświęcony jest problemowi szukania drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym. Jednym z zastosowań jest poszukiwanie optymalnych harmonogramów w równoległym przetwarzaniu zapytań w relacyjnych bazach danych. Podajemy nowe oszacowanie funkcji dobroci przybliżonego algorytmu autorstwa Makino, Uno i Ibaraki wraz z rezultatami testów komputerowych przeprowadzonych dla grafów losowych.
-
Efficient parallel query processing by graph ranking
PublikacjaW artykule analizujemy przybliżony algorytm dla problemu szukania drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym, co znajduje zastosowanie w równoległym przetwarzaniu zapytań w relacyjnych bazach danych. Podajemy nowe oszacowanie uporządkowanego indeksu chromatycznego drzewa, które prowadzi do uzyskania lepszej funkcji dobroci wspomnianego algorytmu.
-
The complexity of node blocking for dags
PublikacjaRozważamy następującą grę (pomiędzy dwoma graczami) kombinatoryczną o nazwie ''node blocking''. Dany jest graf skierowany. Każdy wierzchołek może być zajęty przez co najwyżej jeden token. Wyróżniamy dwa kolory tokenów, biały i czarny, każdy gracz może przemieszczać tylko własne tokeny. Gracze wykonują ruchy naprzemiennie. Ruch polega na wyborze dowolnego tokena własnego koloru i przesunięciu go na dowolnego niezajętego przez inny...
-
The complexity of bicriteria tree-depth
PublikacjaThe tree-depth problem can be seen as finding an elimination tree of minimum height for a given input graph G. We introduce a bicriteria generalization in which additionally the width of the elimination tree needs to be bounded by some input integer b. We are interested in the case when G is the line graph of a tree, proving that the problem is NP-hard and obtaining a polynomial-time additive 2b-approximation algorithm. This particular...
-
The complexity of list ranking of trees
PublikacjaUporządkowane kolorowanie grafu polega na takim etykietowaniu jego wierzchołków, aby każda ścieżka łącząca dwa wierzchołki o tym samym kolorze zawierała wierzchołek o kolorze wyższym. Jeśli każdy wierzchołek posiada dodatkowo listę dozwolonych dla niego etykiet, to mówimy wówczas o uporządkowanym listowym kolorowaniu wierzchołków. W pracy wskazano szereg klas grafów, dla których problem jest trudny: pełne drzewa binarne, drzewa...
-
Complexity of resilient network optimisation
Publikacja -
On the complexity of resilient network design
Publikacja -
On the complexity of distributed greedy coloring
PublikacjaW pracy rozważono problem kolorowania grafów przy dodatkowym założeniu, że kolor żadnego wierzchołka nie może zostać zmniejszony bez zmiany kolorów przynajmniej jednego z jego sąsiadów. Przeprowadzone rozważania dotyczyły złożoności obiczeniowej problemu w modelu Liniala obliczeń rozproszonych. Podano ograniczenia dolne i górne złożoności problemu oraz zestawiono problem z innymi pokrewnymi zagadnieniami grafowymi.
-
The clinical complexity of patients with acromegaly
Publikacja -
Management of complexity and information flow
PublikacjaProblemy złożoności i zarządzania przepływem informacji. W rozdziale omówio-no podejście do modelowania systemów złożonych oraz zarządzania przepływeminformacji w takich systemach. Rozwiązania odniesiono do płaszczyzny elasty-cznego wytwarzania. Poruszono aspekty miękkiego modelowania w takich środo-wiskach.
-
Interactive Query Expansion with the Use of Clustering by Directions Algorithm
PublikacjaThis paper concerns Clustering by Directions algorithm. The algorithm introduces a novel approach to interactive query expansion. It is designed to support users of search engines in forming web search queries. When a user executes a query, the algorithm shows potential directions in which the search can be continued. This paper describes the algorithm and it presents an enhancement which reduces the computational complexity of...
-
Query by Shape for Image Retrieval from Multimedia Databases
Publikacja -
Query-by-Shape interface for Content Based Image Retrieval
Publikacja -
Algorithms for query processing in a distributed knowledge integration system
PublikacjaGłównym celem artykułu jest wprowadzenie modelu systemu integracji wiedzy. Przedstawiony model jest oparty na modelu Calvanese i rozszerza go o wielowarstwowy model integracji. W artykule pokazano również użycie Kartograficznej Reprezentacji Wiedzy do przechowywania i przetwarzania ontologii w źródłach wiedzy oraz do budowania odwzorowań pomiędzy ontologiami. Odwzorowania pomiędzy ontologiami budowane w oparciu o odwzorowywanie...
-
Algorithms for query processing in a distributed knowledge integration system
Publikacja -
Music query and annotation processes supported by gaze fixation tracking
PublikacjaCelem referatu jest przegląd kluczowych zagadnień związanych z automatycznym wyszukiwaniem informacji muzycznej MIR - Music Information Retrieval. W pierwszej kolejności przedstawiono aktualne kierunki badań i rozwiązań systemowych związane z wyszukiwaniem i rekomendacją muzyki. Następnie zaprezentowano eksperymenty przeprowadzone na skonstruowanej bazie muzycznej. Pokazano również propozycję wspomagania procesu wyszukiwania i...
-
Music query and annotation processes supported by gaze fixation tracking
PublikacjaCelem artykułu jest przegląd kluczowych zagadnień związanych z automatycznym wyszukiwaniem informacji muzycznej MIR - Music Information Retrieval. W pierwszej kolejności przedstawiono aktualne kierunki badań i rozwiązań systemowych związane z wyszukiwaniem i rekomendacją muzyki. Następnie zaprezentowano eksperymenty przeprowadzone na skonstruowanej bazie muzycznej. Pokazano również propozycję wspomagania procesu wyszukiwania i...
-
Modularized Knowledge Bases Using Contexts, Conglomerates and a Query Language
PublikacjaArtykuł prezentuje nowatorskie podejście do projektowania i budowy baz wiedzy, zorientowane na wyróżnianie kontekstów i ich implementację za pomocą semantycznych modułów wiedzy zwanych konglomeratami.
-
Content Based Image Retrieval using Query by Approximate Shape
Publikacja -
The Complexity of Zero-Visibility Cops and Robber
PublikacjaIn this work we deal with the computational complexity aspects of the zero-visibility Cops and Robber game. We provide an algorithm that computes the zero-visibility copnumber of a tree in linear time and show that the corresponding decision problem is NP-complete even for the class of starlike graphs.
-
The complexity of minimum-length path decompositions
PublikacjaWe consider a bi-criteria generalization of the pathwidth problem, where, for given integers k, l and a graph G, we ask whether there exists a path decomposition P of G such that the width of P is at most k and the number of bags in P, i.e., the length of P, is at most l. We provide a complete complexity classification of the problem in terms of k and l for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter...
-
The complexity of zero-visibility cops and robber
PublikacjaWe consider the zero-visibility cops & robber game restricted to trees. We produce a characterisation of trees of copnumber k and We consider the computational complexity of the zero-visibility Cops and Robber game. We present a heavily modified version of an already-existing algorithm that computes the zero-visibility copnumber of a tree in linear time and we show that the corresponding decision problem is NP-complete on a nontrivial...
-
Complexity Issues on of Secondary Domination Number
PublikacjaIn this paper we study the computational complexity issues of the problem of secondary domination (known also as (1, 2)-domination) in several graph classes. We also study the computational complexity of the problem of determining whether the domination and secondary domination numbers are equal. In particular, we study the influence of triangles and vertices of degree 1 on these numbers. Also, an optimal algorithm for finding...
-
Complexity of a classical flow restoration problem
Publikacja -
The complexity of equitable vertex coloring graphs
PublikacjaW artykule podajemy wzory na sprawiedliwą liczbę chromatyczną niektórych produktów grafowych. Ponadto przedstawiamy dwa algorytmy wielomianowe dla sprawiedliwego kolorowania grafów suboptymalną liczba kolorów.
-
World Wide Web CBIR Searching Using Query by Approximate Shapes
Publikacja -
Clinical complexity – where to find it and how to use it
Publikacja -
Edge and Pair Queries-Random Graphs and Complexity
PublikacjaWe investigate two types of query games played on a graph, pair queries and edge queries. We concentrate on investigating the two associated graph parameters for binomial random graphs, and showing that determining any of the two parameters is NP-hard for bounded degree graphs.
-
Complexity of weak acceptonic conditions in tree automata
PublikacjaRozważano złożoność problemu pustości dla automatów na drzewach ze słabymi warunkami akceptowalności. Rozważano także translacje pomiędzy słabymi i silnymi warunkami akceptowalności.
-
Constant-Factor Approximation Algorithm for Binary Search in Trees with Monotonic Query Times
PublikacjaWe consider a generalization of binary search in linear orders to the domain of weighted trees. The goal is to design an adaptive search strategy whose aim is to locate an unknown target vertex of a given tree. Each query to a vertex v incurs a non-negative cost ω(v) (that can be interpreted as the duration of the query) and returns a feedback that either v is the target or the edge incident to v is given that is on the path towards...
-
Query-by-Shape Interface for Content Based Image Retrieval Based on Shape Analysis
Publikacja -
Automatic detection and correction of detuned singing system for use with query-by-humming applications
PublikacjaThe aim of the paper is to present an idea of using the automatic detection and correction of detuned singing as a subsystem in query-by-humming (QBH) applications. The common approach to searching for a requested song basing on the melody retrieved from hummed pattern usually employs the so-called Parsons code or melody contour. In such a case information about sound pitch is discarded. It was thought out that an additional module...
-
Automatic detection and correction of detuned singing system for use with query-by-humming applications
PublikacjaThe aim of the paper is to present an idea of using the automatic detection and correction of detuned singing as a subsystem in query-by-humming (QBH) applications. The common approach to searching for a requested song basing on the melody retrieved from hummed pattern usually employs the so-called Parsons code or melody contour. In such a case information about sound pitch is discarded. It was thought out that an additional module...
-
ANALYSIS OF EFFECTIVENESS AND COMPUTATIONAL COMPLEXITY OF TREND REMOVAL METHODS
PublikacjaThe paper presents a method of processing measurement data due to remove slowly varying component of the trend occurring in the recorded waveforms. Comparison of computational complexity and trend removal efficiency between some commonly used methods is presented. The impact of these procedures on probability distribution and power spectral density is shown. Effectiveness and computational complexity of these methods depend essentially...
-
On the complexity of distributed graph coloring with local minimality constraints
PublikacjaArtykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Omówiono algorytmy rozproszone, dające w wyniku pokolorowanie spełniające warunki dla pokolorowań sekwencyjnych typu S oraz Largest-First (LF). Udowodniono również, że każda rozproszona implementacja algorytmu S wymaga co najmniej Omega(log n / log log n) rund, a algorytmu LF co najmniej Omega (n^{1/2}) rund, gdzie n oznacza liczbę wierzchołków grafu.
-
Scheduling jobs to contain a natural disaster: a model and complexity
Publikacjathis paper is devoted to the problem of scheduling suppression units so that a natural disaster is dealt with as efficient as possible. the concept of deteriorating jobs is adopted, that is, the formal model of scheduling represents linearly increasing value loss as the disaster remains unsuppressed and increasing time for its suppression. more precisely, two different goals are considered: finding a suppression schedule of minimal...
-
Review of the Complexity of Managing Big Data of the Internet of Things
PublikacjaTere is a growing awareness that the complexity of managing Big Data is one of the main challenges in the developing feld of the Internet of Tings (IoT). Complexity arises from several aspects of the Big Data life cycle, such as gathering data, storing them onto cloud servers, cleaning and integrating the data, a process involving the last advances in ontologies, such as Extensible Markup Language (XML) and Resource Description...
-
The complexity of the T-coloring problem for graphs with small degree.
PublikacjaW pracy ustalono złożoność obliczeniową problemu optymalnego kolorowania grafów o ustalonym stopniu.
-
Smart systems integration: toward overcoming the problem of complexity
PublikacjaW pracy omówiono modelowa propozycję integracji systemu opartą na zastosowaniu sztucznej inteligencji w celu rozwiązania problemu złożoności systemowej.
-
The complexity of the T-coloring problem for graphs with small degree
Publikacja -
Some results concerning the complexity of restricted colorings of graphs
Publikacja -
The laws of thermodynamics: entropy, free energy, information and complexity
PublikacjaW rozdziale przedstawiono podstawowe Zasady Termodynamiki. Omówiono zagadnienia związane z pojęciem entropii, energii Gibbsa, egzergii oraz systemami złożonymi.
-
New Content Based Image Retrieval database structure using Query by Approximate Shapes
Publikacja -
Quantum communication complexity advantage implies violation of a Bell inequality
PublikacjaWe obtain a general connection between a quantum advantage in communication complexity and non-locality. We show that given any protocol offering a (sufficiently large) quantum advantage in communication complexity, there exists a way of obtaining measurement statistics which violate some Bell inequality. Our main tool is port-based teleportation. If the gap between quantum and classical communication complexity can grow arbitrarily...
-
Teaching Architecture – contemporary challenges and threats in the complexity of built environment
PublikacjaThe complexity of the modern built environment is a problem n ot only of architectural and urban issues. This issue extends to many othe r disciplines as well as covering a wide range of social engagements. The idea of writing this pa per is generally initiated by the debate which took place in Gdańs k on 22.01.2016, and was prepar ed in order to meet representatives of the four circles of interest...
-
Reduction of Computational Complexity in Simulations of the Flow Process in Transmission Pipelines
PublikacjaThe paper addresses the problem of computational efficiency of the pipe-flow model used in leak detection and identification systems. Analysis of the model brings attention to its specific structure, where all matrices are sparse. With certain rearrangements, the model can be reduced to a set of equations with tridiagonal matrices. Such equations can be solved using the Thomas algorithm. This method provides almost the same values...
-
A low complexity double-talk detector based on the signal envelope
PublikacjaA new algorithm for double-talk detection, intended for use in the acoustic echo canceller for voice communication applications, is proposed. The communication system developed by the authors required the use of a double-talk detection algorithm with low complexity and good accuracy. The authors propose an approach to doubletalk detection based on the signal envelopes. For each of three signals: the far-end speech, the microphone...
-
The final answer to the complexity of a basic problem in resilient network design
Publikacja -
Farrow structure for complex digital Hilbert filter of low complexity
PublikacjaW pracy przeanalizowano złożoność numeryczną filtru Hilberta (filtr zespolony), złożonego z pary filtrów cyfrowych o zmiennym opóźnieniu ułamkowym, o strukturze Farrowa. Struktura ta pozwala na zmianę opóźnienia ułamkowego na bieżąco, bez potrzeby każdorazowego przeprojektowywania filtru. Zaproponowano algorytmy/struktury wykorzystujące nie tylko symetrię oryginalnej struktury Farrowa, ale również wspólne elementy opóźniające podfiltrów...