Wyszukiwarka
Filtry
wszystkich: 159
Wyniki wyszukiwania dla: polynomial algorithm.
-
Towards Changes of Macro-Economic Structures in Middle Eastern Countries. Empirical Evidence for 1970–2018
PublikacjaMiddle East countries share a wide bundle of specific structural economic features and one of the latest is a high dependency of these economies on fossil fuels, which is quantitatively demonstrated through the share of oil and gas revenues in total export, but also in gross domestic product composition. This high economic dependency on natural resources on one hand has recently generated a material wealth of Middle Eastern countries...
-
Bridge Non-Destructive Measurements Using a Laser Scanning during Acceptance Testing: Case Study
PublikacjaOwing to the recent proliferation of inventory works on roads and railways, bridge acceptance tests have increased exponentially. These tests’ results are often misinterpreted owing to the use of various measuring equipment types, rendering integrated interpretation problematic. It is also problematic that adjusting the measurement method is difficult when the structure’s response to load is uncertain. Therefore, it is important...
-
Fast collaborative graph exploration
PublikacjaWe 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...
-
Fast Collaborative Graph Exploration
PublikacjaWe 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
PublikacjaStructural 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,...
-
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
PublikacjaWe 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
PublikacjaW 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
PublikacjaWe 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
PublikacjaThe 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.