THEORETICAL COMPUTER SCIENCE - Czasopismo - MOST Wiedzy

Wyszukiwarka

THEORETICAL COMPUTER SCIENCE

ISSN:

0304-3975

eISSN:

1879-2294

Dyscypliny:

  • Informatyka techniczna i telekomunikacja (Dziedzina nauk inżynieryjno-technicznych)
  • Informatyka (Dziedzina nauk ścisłych i przyrodniczych)

Punkty Ministerialne: Pomoc

Punkty Ministerialne - aktualny rok
Rok Punkty Lista
Rok 2024 100 Ministerialna lista czasopism punktowanych 2024
Punkty Ministerialne - lata ubiegłe
Rok Punkty Lista
2024 100 Ministerialna lista czasopism punktowanych 2024
2023 100 Lista ministerialna czasopism punktowanych 2023
2022 100 Lista ministerialna czasopism punktowanych (2019-2022)
2021 100 Lista ministerialna czasopism punktowanych (2019-2022)
2020 100 Lista ministerialna czasopism punktowanych (2019-2022)
2019 100 Lista ministerialna czasopism punktowanych (2019-2022)
2018 20 A
2017 20 A
2016 20 A
2015 20 A
2014 20 A
2013 20 A
2012 25 A
2011 25 A
2010 27 A

Model czasopisma:

Hybrydowe

Punkty CiteScore:

Punkty CiteScore - aktualny rok
Rok Punkty
Rok 2022 2.5
Punkty CiteScore - lata ubiegłe
Rok Punkty
2022 2.5
2021 2.1
2020 1.9
2019 2.3
2018 2.4
2017 2.1
2016 1.8
2015 2
2014 2.1
2013 2
2012 2.1
2011 2.1

Impact Factor:

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

Filtry

wszystkich: 24

  • Kategoria
  • Rok
  • Opcje

wyczyść Filtry wybranego katalogu niedostępne

Katalog Czasopism

  • Weighted 2-sections and hypergraph reconstruction
    Publikacja

    In the paper we introduce the notion of weighted 2-sections of hypergraphs with integer weights and study the following hypergraph reconstruction problems: (1) Given a weighted graph , is there a hypergraph H such that is its weighted 2-section? (2) Given a weighted 2-section , find a hypergraph H such that is its weighted 2-section. We show that (1) is NP-hard even if G is a complete graph or integer weights w does not exceed...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Gossiping by energy-constrained mobile agents in tree networks
    Publikacja

    - THEORETICAL COMPUTER SCIENCE - Rok 2021

    Every node of an edge-weighted tree network contains a data packet. At some nodes are placed mobile agents, each one possessing an amount of energy (not necessarily the same for all agents). While walking along the network, the agents spend the energy proportionally to the distance traveled and collect copies of the data packets present at the visited network nodes. An agent visiting a node deposits there copies of all currently...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Consensus models: Computational complexity aspects in modern approaches to the list coloring problem

    Artykuł poświęcony jest nowym modelom konsensusowego kolorowania grafów. Artykuł zawiera omówienie trzech takich modeli, analizę ich złożoności obliczeniowej oraz wielomianowy algorytm dla częściowych k-drzew, dla tzw. modelu addytywnego.

    Pełny tekst do pobrania w portalu

  • 2-Coloring number revisited

    2-Coloring number is a parameter, which is often used in the literature to bound the game chromatic number and other related parameters. However, this parameter has not been precisely studied before. In this paper we aim to fill this gap. In particular we show that the approximation of the game chromatic number by the 2-coloring number can be very poor for many graphs. Additionally we prove that the 2-coloring number may grow...

    Pełny tekst do pobrania w portalu

  • Finite automata for compact representation of tuple dictionaries.
    Publikacja

    - THEORETICAL COMPUTER SCIENCE - Rok 2004

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

    Pełny tekst do pobrania w portalu

  • Rank two bibartite bound entangled states do not exist.
    Publikacja

    - THEORETICAL COMPUTER SCIENCE - Rok 2003

    Wykazano, że nie istnieją stany rzędu dwa które zawierałyby splątanie. Pokazano związki między lokalnym a globalnym rzędem macierzy gęstości oraz ewentualną możliwością wydestylowania kwantowego splątania.

    Pełny tekst do pobrania w portalu

  • The complexity of bicriteria tree-depth
    Publikacja

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

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Phutball is PSPACE-hard

    W pracy dowodzimy, że gra ''Phutball'' (Philosopher's Football) jest PSPACE-trudna.

    Pełny tekst do pobrania w portalu

  • The searchlight problem for road networks
    Publikacja

    - THEORETICAL COMPUTER SCIENCE - Rok 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 do pobrania w portalu

  • 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 do pobrania w portalu

  • Finding small-width connected path decompositions in polynomial time
    Publikacja

    A connected path decomposition of a simple graph $G$ is a path decomposition $(X_1,\ldots,X_l)$ such that the subgraph of $G$ induced by $X_1\cup\cdots\cup X_i$ is connected for each $i\in\{1,\ldots,l\}$. The connected pathwidth of $G$ is then the minimum width over all connected path decompositions of $G$. We prove that for each fixed $k$, the connected pathwidth of any input graph can be computed in polynomial-time. This answers...

    Pełny tekst do pobrania w portalu

  • Brushing with additional cleaning restrictions
    Publikacja

    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 do pobrania w portalu

  • 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 do pobrania w portalu

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

    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 do pobrania w portalu

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

    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 do pobrania w portalu

  • Smaller representation of finite state automata
    Publikacja

    - THEORETICAL COMPUTER SCIENCE - Rok 2012

    This paper is a follow-up to Jan Daciuk's experiments on space-efficient finite state automata representation that can be used directly for traversals in main memory (Daciuk, 2000)[4]. We investigate several techniques for reducing memory footprint of minimal automata, mainly exploiting the fact that transition labels and transition pointer offset values are not evenly distributed and so are suitable for compression. We achieve...

    Pełny tekst do pobrania w portalu

  • Cops, a fast robber and defensive domination on interval graphs
    Publikacja

    - THEORETICAL COMPUTER SCIENCE - Rok 2019

    The game of Cops and ∞-fast Robber is played by two players, one controlling c cops, the other one robber. The players alternate in turns: all the cops move at once to distance at most one each, the robber moves along any cop-free path. Cops win by sharing a vertex with the robber, the robber by avoiding capture indefinitely. The game was proposed with bounded robber speed by Fomin et al. in “Pursuing a fast robber on a graph”,...

    Pełny tekst do pobrania w portalu

  • 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 do pobrania w portalu

  • Approximate search strategies for weighted trees

    W pracy podajemy 3-przybliżony algorytm dla problemu spójnego przeszukiwania drzew ważonych.

    Pełny tekst do pobrania w portalu

  • Synchronous black hole search in directed graphs
    Publikacja

    - THEORETICAL COMPUTER SCIENCE - Rok 2011

    The paper considers a team of robots which has to explore a graph G, where some nodes can be harmful. Robots are initially located at the so-called home base node. The dangerous nodes are the so-called black hole nodes, and once a robot enters in one of them, it is destroyed. The goal is to find a strategy in order to explore G in such a way that minimum number of robots is wasted. The exploration ends if there is at least one...

    Pełny tekst do pobrania w portalu

  • The complexity of zero-visibility cops and robber
    Publikacja

    - THEORETICAL COMPUTER SCIENCE - Rok 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 do pobrania w portalu

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

    - THEORETICAL COMPUTER SCIENCE - Rok 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 do pobrania w portalu

  • Connected searching of weighted trees

    W pracy pokazano, że problem spójnego przeszukiwania drzew ważonych jest silnie NP-zupełny. Problem pozostaje trudnym dla drzew z jednym wierzchołkiem o stopniu większym niż 2. Ponadto, przedstawiony został wielomianowy optymalny algorytm dla klasy drzew z ograniczonym stopniem.

    Pełny tekst do pobrania w portalu

  • Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring
    Publikacja

    - THEORETICAL COMPUTER SCIENCE - Rok 2010

    One of the recently considered models of robot-based computing makes use of identical, memoryless mobile units placed in nodes of an anonymous graph. The robots operate in Look-Compute-Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), takes a decision whether to stay idle or to move to one of the nodes adjacent to its current position (Compute), and in the latter case makes an instantaneous...

    Pełny tekst do pobrania w portalu

wyświetlono 739 razy