In this work we consider the edge searching problem for vertex-weighted graphs with arbitrarily fast and invisible fugitive. The weight function $${\omega }$$ provides for each vertex $$v$$ the minimum number of searchers required to guard $$v$$ , i.e., the fugitive may not pass through $$v$$ without being detected only if at least $${\omega }(v)$$ searchers are present at $$v$$ . This problem is a generalization of the classical edge searching problem, in which one has $${\omega }\equiv 1$$ . We assume that with a graph $$G$$ to be searched, there is associated a partition $$(V_1,\ldots ,V_t)$$ of its vertex set such that edges are allowed only within each $$V_i$$ and between two consecutive $$V_i$$ ’s. We provide an algorithm for distributed monotone connected edge searching of such graphs, where the searchers are initially placed on an arbitrary vertex of $$G$$ and have no a priori knowledge on $$G$$ , but they have a sense of direction that lets them recognize whether an edge incident to already explored vertex in $$V_i$$ leads to a vertex in one of $$V_{i-1}, V_i$$ or $$V_{i+1}$$ . Starting from any vertex the algorithm uses at most $$3\cdot \max _{i=1,\ldots ,t}{\omega }(V_i)+1$$ searchers, where $${\omega }(V_i) = \sum _{v\in V_i}{\omega }(v)$$ . We also prove that this algorithm is best possible up to a small additive constant, that is, each distributed searching algorithm in worst case must use $$3\cdot \max _{i=1,\ldots ,t}{\omega }(V_i)-1$$ searchers for some graphs.

Dynamics is an inherent feature of many real life systems so it is natural to define and investigate the properties of models that reflect their dynamic nature. Dynamic graph colorings can be naturally applied in system modeling, e.g. for scheduling threads of parallel programs, time sharing in wireless networks, session scheduling in high-speed LAN's, channel assignment in WDM optical networks as well as traffic scheduling. In the dynamic setting of the problem, a graph we color is not given in advance and new vertices together with adjacent edges are revealed one after another at algorithm's input during the coloring process. Moreover, independently of the algorithm, some vertices may lose their colors and the algorithm may be asked to color them again. We formally define a dynamic graph coloring problem, the dynamic chromatic number and prove various bounds on its value. We also analyze the effectiveness of the dynamic coloring algorithm Dynamic-Fit for selected classes of graphs. In particular, we deal with trees, products of graphs and classes of graphs for which Dynamic-Fit is competitive. Motivated by applications, we state the problem of dynamic coloring with discoloring constraints for which the performance of the dynamic algorithm Time-Fit is analyzed and give a characterization of graphs k-critical for Time-Fit. Since for any fixed k > 0 the number of such graphs is finite, it is possible to decide in polynomial time whether Time-Fit will always color a given graph with at most k colors.