THEORETICAL COMPUTER SCIENCE - Czasopismo - MOST Wiedzy

Wyszukiwarka

Theoretical computer science

Weryfikacja:

Politechnika Gdańska

Punkty ministerialne:

Punkty Ministerialne
2019 100 MNiSW 2019

Punkty Ministerialne
Rok Punkty Lista
2019 100 MNiSW 2019
2017 20 A
2016 20 A
2015 20 A
2014 20 A
2013 20 A
2011 25 A
2008 27 A

Impact Factor:

Zaloguj się aby zobaczyć Współczynnik Impact Factor dla tego czasopisma

Polityki wydawnicze:

Brak danych

ISSN:

0304-3975

Filtry

wszystkich: 18

  • Kategoria
  • Rok

Katalog Czasopism

2016
  • Topology recognition and leader election in colored networks
    Publikacja

    Topology recognition and leader election are fundamental tasks in distributed computing in networks. The first of them requires each node to find a labeled isomorphic copy of the network, while the result of the second one consists in a single node adopting the label 1 (leader), with all other nodes adopting the label 0 and learning a path to the leader. We consider both these problems in networks whose nodes are equipped with...

    Pełny tekst w serwisie zewnętrznym

2015
  • Distinguishing views in symmetric networks: A tight lower bound

    The view of a node in a port-labeled network is an infinite tree encoding all walks in the network originating from this node. We prove that for any integers n ≥ D ≥ 1, there exists a port-labeled network with at most n nodes and diameter at most D which contains a pair of nodes whose (infinite) views are different, but whose views truncated to depth Omega( D log(n/ D )) are identical.

    Pełny tekst w serwisie zewnętrznym

  • Rendezvous of heterogeneous mobile agents in edge-weighted networks

    We introduce a variant of the deterministic rendezvous problem for a pair of heterogeneous agents operating in an undirected graph, which differ in the time they require to traverse particular edges of the graph. Each agent knows the complete topology of the graph and the initial positions of both agents. The agent also knows its own traversal times for all of the edges of the graph, but is unaware of the corresponding traversal...

    Pełny tekst w serwisie zewnętrznym

  • The complexity of zero-visibility cops and robber
    Publikacja

    - THEORETICAL COMPUTER SCIENCE - 2015

    We 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...

    Pełny tekst w serwisie zewnętrznym

  • The searchlight problem for road networks
    Publikacja

    - THEORETICAL COMPUTER SCIENCE - 2015

    We consider the problem of searching for a mobile intruder hiding in a road network given as the union of two or more lines, or two or more line segments, in the plane. Some of the intersections of the road network are occupied by stationary guards equipped with a number of searchlights, each of which can emit a single ray of light in any direction along the lines (or line segments) it is on. The goal is to detect the intruder,...

    Pełny tekst w serwisie zewnętrznym

2014
  • Brushing with additional cleaning restrictions

    In graph cleaning problems, brushes clean a graph by traversing it subject to certain rules. We consider the process where at each time step, a vertex that has at least as many brushes as incident, contaminated edges, sends brushes down these edges to clean them. Various problems arise, such as determining the minimum number of brushes (called the brush number) that are required to clean the entire graph. Here, we study a new variant...

    Pełny tekst w serwisie zewnętrznym

2013
  • On minimum cost edge searching
    Publikacja

    We consider the problem of finding edge search strategies of minimum cost. The cost of a search strategy is the sum of searchers used in the clearing steps of the search. One of the natural questions is whether it is possible to find a search strategy that minimizes both the cost and the number of searchers used to clear a given graph G. We call such a strategy ideal. We prove, by an example, that ideal search strategies do not...

    Pełny tekst w serwisie zewnętrznym

2012
2011
2010
2009
  • Universal Augmentation Schemes for Network Navigability
    Publikacja
    • P. Fraigniaud
    • C. Gavoille
    • A. Kosowski
    • E. Lebhar
    • Z. Lotker

    - THEORETICAL COMPUTER SCIENCE - 2009

    Rozważano problem uzupełniania grafu (reprezentującego np. sieci społeczne) poprzez dodanie w każdym węźle jednego dodatkowego skierowanego połączenia (długodystansowego). Dokładniej, dla każdego węzła definiuje się listę prawdopodobieństw istnienia połączenia wychodzącego z danego węzła do wszystkich pozostałych węzłów; wartości tych prawdopodobieństw muszą sumować się do jedności. Routing zachłanny w takiej sieci polega na przekazywaniu...

    Pełny tekst w serwisie zewnętrznym

2008
  • The maximum edge-disjoint paths problem in complete graphs

    Rozważono problem ścieżek krawędziowo rozłącznych w grafach pełnych. Zaproponowano wielomianowe algorytmy: 3.75-przybliżony (off-line) oraz 6.47-przybliżony (on-line), poprawiając tym samym wyniki wcześniej znane z literatury [P. Carmi, T. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs, in: Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science, in: LNCS, vol. 2880, 2003, pp. 143-155]. Ponadto...

    Pełny tekst w serwisie zewnętrznym

2004
  • Finite automata for compact representation of tuple dictionaries.
    Publikacja

    Opisane zostaje uogólnienie struktury danych - słownika, zwane słownikiem n-tek. Słownik n-tek przedstawia odwzorowanie n-tek łańcuchów znaków na pewne wartości. Motywacją dla powstania tej struktury danych są praktyczne zastosowania w przetwarzaniu języka i mowy, w których obszerne słowniki n-tek używane są do przedstawiania modeli języka. Przedstawiona zostaje technika oszczędnej reprezentacji słowników n-tek. Ta technika...

2003

wyświetlono 30 razy