Search
Search results for: polynomial algorithm
-
Fast collaborative graph exploration
PublicationWe study the following scenario of online graph exploration. A team of k agents is initially located at a distinguished vertex r of an undirected graph. At every time step, each agent can traverse an edge of the graph. All vertices have unique identifiers, and upon entering a vertex, an agent obtains the list of identifiers of all its neighbors. We ask how many time steps are required to complete exploration, i.e., to make sure...
-
Normal-form preemption sequences for an open problem in scheduling theory
PublicationStructural properties of optimal preemptive schedules have been studied in a number of recent papers with a primary focus on two structural parameters: the minimum number of preemptions necessary, and a tight lower bound on shifts, i.e., the sizes of intervals bounded by the times created by preemptions, job starts, or completions. These two parameters have been investigated for a large class of preemptive scheduling problems,...
-
Fast Collaborative Graph Exploration
PublicationWe study the following scenario of online graph exploration. A team of k agents is initially located at a distinguished vertex r of an undirected graph. At every time step, each agent can traverse an edge of the graph. All vertices have unique identifiers, and upon entering a vertex, an agent obtains the list of identifiers of all its neighbors. We ask how many time steps are required to complete exploration, i.e., to make sure...
-
On the derivatives $\partial^{2}P_{\nu}(z)/\partial\nu^{2}$ and $\partial Q_{\nu}(z)/\partial\nu$ of the Legendre functions with respect to their degrees
PublicationWe provide closed-form expressions for the degree-derivatives $[\partial^{2}P_{\nu}(z)/\partial\nu^{2}]_{\nu=n}$ and $[\partial Q_{\nu}(z)/\partial\nu]_{\nu=n}$, with $z\in\mathbb{C}$ and $n\in\mathbb{N}_{0}$, where $P_{\nu}(z)$ and $Q_{\nu}(z)$ are the Legendre functions of the first and the second kind, respectively. For $[\partial^{2}P_{\nu}(z)/\partial\nu^{2}]_{\nu=n}$, we find that % \begin{displaymath} \frac{\partial^{2}P_{\nu}(z)}{\partial\nu^{2}}\bigg|_{\nu=n} =-2P_{n}(z)\Li_{2}\frac{1-z}{2}+B_{n}(z)\ln\frac{z+1}{2}+C_{n}(z), \end{displaymath} % where...
-
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
PublicationW artykule rozważamy listowo-kosztowe kolorowanie wierzchołków i krawędzi grafu w modelu wierzchołkowym, krawędziowym, totalnym i pseudototalnym. Stosujemy programowanie dynamiczne w celu otrzymania algorytmów wielomianowych dla drzew. Następnie uogólniamy to podejście na dowolne grafy z ograniczonymi liczbami cyklomatycznymi i na ich multikolorowania.
-
Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs
PublicationWe consider the complexity of semi-equitable k-coloring, k>3, of the vertices of a cubic or subcubic graph G. In particular, we show that, given a n-vertex subcubic graph G, it is NP-complete to obtain a semi-equitable k-coloring of G whose non-equitable color class is of size s if s>n/3, and it is polynomially solvable if s, n/3.
-
Equitable colorings of some variation of corona products of cubic graphs
PublicationThe problem of determining the value of equitable chromatic number for multicoronas of cubic graphs is studied. We provide some polynomially solvable cases of cubical multicoronas and give simple linear time algorithms for equitable coloring of such graphs which use almost optimal number of colors in the remaining cases.