(Field of Science):
- Information and communication technology (Engineering and Technology)
- Civil engineering and transport (Engineering and Technology)
- Computer and information sciences (Natural sciences)
Ministry points: Help
|2020||100||Ministry Scored Journals List 2019|
|2019||100||Ministry Scored Journals List 2019|
- author's version of the article before the review
- author's version of the article after the review
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|
Papers published in journal
We study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset S of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph H=(V,A) of D such that (a) S is a subset of V, (b) H is the union of k directed...
Mobile agents start at different nodes of an n-node network. The agents synchronously move along the network edges in a collision-free way, i.e., in no round two agents may occupy the same node. An agent has no knowledge of the number and initial positions of other agents. We are looking for the shortest time required to reach a configuration in which each agent has visited all nodes and returned to its starting location. In...
The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node successively propagates walkers visiting it along its outgoing arcs in round-robin fashion, according to a fixed ordering. We consider...
We 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 classiﬁcation of the problem in terms of k and l for general graphs. Contrary to the original pathwidth problem, which is ﬁxed-parameter...
seen 74 times