# THEORETICAL COMPUTER SCIENCE - Journal - MOST Wiedzy

## THEORETICAL COMPUTER SCIENCE

0304-3975

1879-2294

### Disciplines (Field of Science):

• Information and communication technology (Engineering and Technology)
• Computer and information sciences (Natural sciences)

### Ministry points: Help

 2020 100 Ministry Scored Journals List 2019
Ministry points
Year Points List
2020 100 Ministry Scored Journals List 2019
2019 100 Ministry Scored Journals List 2019
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
2009 27 A
2008 27 A

Hybrid

### Punkty CiteScore:

 2018 1.23
Punkty CiteScore
Year Points
2018 1.23
2017 1.08
2016 0.97

### Publishing policy:

SHERPA RoMEO status
Pre-print
author's version of the article before the review
Post-print
author's version of the article after the review

### Status table SHERPA RoMEO

Status table SHERPA RoMEO
RoMEO color Archiving policy
Green can archive pre-prints and post-prints or a version of the publisher
Blue can archive post-prints
Yellow can archive pre-prints
White can not archive any materials
Gray unknown

### Papers published in journal

• results on page:
• year:
title:
citation:

total: 21

#### Catalog Journals

##### 2019
• ###### 2-Coloring number revisited
Publication

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

Full text in external service

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

- THEORETICAL COMPUTER SCIENCE - 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”,...

Full text in external service

• ###### Finding small-width connected path decompositions in polynomial time
Publication

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

Full text in external service

##### 2016
• ###### Topology recognition and leader election in colored networks
Publication

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

Full text in external service

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

Full text in external service

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

Full text in external service

• ###### The complexity of zero-visibility cops and robber
Publication

- THEORETICAL COMPUTER SCIENCE - 2015

We consider the zero-visibility cops &amp; 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...

Full text in external service

• ###### The searchlight problem for road networks
Publication

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

Full text in external service

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

Full text in external service

##### 2013
• ###### On minimum cost edge searching
Publication

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

Full text in external service

##### 2012
• ###### Approximate search strategies for weighted trees
Publication

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

Full text in external service

• ###### Smaller representation of finite state automata
Publication

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

Full text in external service

##### 2011
• ###### Connected searching of weighted trees
Publication

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.

Full text in external service

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

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.

Full text in external service

• ###### Phutball is PSPACE-hard
Publication

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

Full text in external service

• ###### Synchronous black hole search in directed graphs
Publication

- THEORETICAL COMPUTER SCIENCE - 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...

Full text in external service

##### 2010
• ###### Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring
Publication

- THEORETICAL COMPUTER SCIENCE - 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...

Full text in external service

##### 2009
• ###### Universal Augmentation Schemes for Network Navigability
Publication
• 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...

Full text in external service

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

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

Full text in external service

##### 2004
• ###### Finite automata for compact representation of tuple dictionaries.
Publication

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
• ###### Rank two bibartite bound entangled states do not exist.
Publication

- THEORETICAL COMPUTER SCIENCE - 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.

seen 124 times