Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "polynomial algorithm" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 21
Tytuł:
An attractive class of bipartite graphs
Autorzy:
Boliac, Rodica
Lozin, Vadim
Powiązania:
https://bibliotekanauki.pl/articles/743515.pdf
Data publikacji:
2001
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
bipartite graphs
structural characterization
polynomial algorithm
Opis:
In this paper we propose a structural characterization for a class of bipartite graphs defined by two forbidden induced subgraphs. We show that the obtained characterization leads to polynomial-time algorithms for several problems that are NP-hard in general bipartite graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2001, 21, 2; 293-301
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Scheduling of Identical Jobs with Bipartite Incompatibility Graphs on Uniform Machines. Computational Experiments
Autorzy:
Duraj, S.
Kopeć, P.
Kubale, M.
Pikies, T.
Powiązania:
https://bibliotekanauki.pl/articles/376001.pdf
Data publikacji:
2017
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
batch scheduling
bipartite graph
polynomial algorithm
uniform machines
Opis:
In this paper, we consider the problem of scheduling unit-length jobs on three or four uniform parallel machines to minimize the schedule length or total completion time. We assume that the jobs are subject to some types of mutual exclusion constraints, modeled by a bipartite graph of a bounded degree. The edges of the graph correspond to the pairs of jobs that cannot be processed on the same machine. Although the problem is generally NP-hard, we show that our problem can be solved to optimality in polynomial time under some restrictions imposed on the number of machines, their speeds, and the structure of the incompatibility graph. The theoretical considerations are accompanied by computer experiments with a certain model of scheduling.
Źródło:
Decision Making in Manufacturing and Services; 2017, 11, 1-2; 53-61
1896-8325
2300-7087
Pojawia się w:
Decision Making in Manufacturing and Services
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Persistency in the Traveling Salesman Problem on Halin graphs
Autorzy:
Lacko, Vladimír
Powiązania:
https://bibliotekanauki.pl/articles/743793.pdf
Data publikacji:
2000
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
persistency
traveling salesman problem
Halin graph
polynomial algorithm
Opis:
For the Traveling Salesman Problem (TSP) on Halin graphs with three types of cost functions: sum, bottleneck and balanced and with arbitrary real edge costs we compute in polynomial time the persistency partition $E_{All}$, $E_{Some}$, $E_{None}$ of the edge set E, where:
$E_{All}$ = {e ∈ E, e belongs to all optimum solutions},
$E_{None}$ = {e ∈ E, e does not belong to any optimum solution} and
$E_{Some}$ = {e ∈ E, e belongs to some but not to all optimum solutions}.
Źródło:
Discussiones Mathematicae Graph Theory; 2000, 20, 2; 231-242
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Note on Polynomial Algorithm for Cost Coloring of Bipartite Graphs with Δ ≤ 4
Autorzy:
Giaro, Krzysztof
Kubale, Marek
Powiązania:
https://bibliotekanauki.pl/articles/31526308.pdf
Data publikacji:
2020-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
bipartite graph
chromatic sum
cost coloring
NP-completeness
polynomial algorithm
Opis:
In the note we consider vertex coloring of a graph in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of coloring is the sum of costs incurred at each vertex. We show that the minimum cost coloring problem for n-vertex bipartite graph of degree Δ ≤ 4 can be solved in O(n2) time. This extends Jansen’s result [K. Jansen, The optimum cost chromatic partition problem, in: Proc. CIAC’97, Lecture Notes in Comput. Sci. 1203 (1997) 25–36] for paths and cycles to subgraphs of biquartic graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 3; 885-891
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A locally polynomial method for solving a system of linear inequalities
Autorzy:
Evtushenko, Yuri
Szkatuła, Krzysztof
Tretyakov, Alexey
Powiązania:
https://bibliotekanauki.pl/articles/2183463.pdf
Data publikacji:
2021
Wydawca:
Polska Akademia Nauk. Instytut Badań Systemowych PAN
Tematy:
linear programming
system of linear inequalities
computational complexity
locally-polynomial algorithm
convergence rate
Opis:
The paper proposes a method for solving systems of linear inequalities. This method determines in a finite number of iterations whether the given system of linear ineqalities has a solution. If it does, the solution for the given system of linear inequalities is provided. The computational complexity of the proposed method is locally polynomial.
Źródło:
Control and Cybernetics; 2021, 50, 2; 301--314
0324-8569
Pojawia się w:
Control and Cybernetics
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Finding Dominating Induced Matchings in P9-Free Graphs in Polynomial Time
Autorzy:
Brandstädt, Andreas
Mosca, Raffaele
Powiązania:
https://bibliotekanauki.pl/articles/32222548.pdf
Data publikacji:
2022-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
dominating induced matching
P 9 -free graphs
polynomial time algorithm
Opis:
Let G = (V, E) be a finite undirected graph. An edge subset E′ ⊆ E is a dominating induced matching (d.i.m.) in G if every edge in E is intersected by exactly one edge of E′. The Dominating Induced Matching (DIM) problem asks for the existence of a d.i.m. in G. The DIM problem is ℕℙ-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree 3 but was solved in linear time for P7-free graphs and in polynomial time for P8-free graphs. In this paper, we solve it in polynomial time for P9-free graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 4; 1139-1162
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Spanning trees with many or few colors in edge-colored graphs
Autorzy:
Broersma, Hajo
Li, Xueliang
Powiązania:
https://bibliotekanauki.pl/articles/971955.pdf
Data publikacji:
1997
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
edge-coloring
spanning tree
matroid (intersection)
complexity
NP-complete
NP-hard
polynomial algorithm
(minimum) dominating set
Opis:
Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, we consider the complexity of finding a spanning tree of G with as many different colors as possible, and of finding one with as few different colors as possible. We show that the first problem is equivalent to finding a common independent set of maximum cardinality in two matroids, implying that there is a polynomial algorithm. We use the minimum dominating set problem to show that the second problem is NP-hard.
Źródło:
Discussiones Mathematicae Graph Theory; 1997, 17, 2; 259-269
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines
Autorzy:
Furmańczyk, H.
Kubale, M.
Powiązania:
https://bibliotekanauki.pl/articles/200295.pdf
Data publikacji:
2017
Wydawca:
Polska Akademia Nauk. Czytelnia Czasopism PAN
Tematy:
equitable coloring
NP-hardness
polynomial algorithm
scheduling
uniform machine
kolorowanie grafów
twardość NP
algorytm wielomianowy
planowanie
Opis:
In the paper we consider the problem of scheduling n identical jobs on 4 uniform machines with speeds s1 ≥ s2 ≥ s3 ≥ s4, respectively. Our aim is to find a schedule with a minimum possible length. We assume that jobs are subject to some kind of mutual exclusion constraints modeled by a bipartite incompatibility graph of degree Δ, where two incompatible jobs cannot be processed on the same machine. We show that the general problem is NP-hard even if s1 = s2 = s3. If, however, Δ ≤ 4 and s1 ≥ 12s2, s2 = s3 = s4, then the problem can be solved to optimality in time O(n1.5). The same algorithm returns a solution of value at most 2 times optimal provided that s1 ≥ 2s2. Finally, we study the case s1 ≥ s2 ≥ s3 = s4 and give a 32/15-approximation algorithm running also in O(n1.5) time.
Źródło:
Bulletin of the Polish Academy of Sciences. Technical Sciences; 2017, 65, 1; 29-34
0239-7528
Pojawia się w:
Bulletin of the Polish Academy of Sciences. Technical Sciences
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
Autorzy:
Giaro, Krzysztof
Kubale, Marek
Powiązania:
https://bibliotekanauki.pl/articles/744404.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cost coloring
dynamic programming
list coloring
NP-completeness
polynomial-time algorithm
Opis:
We consider a list cost coloring of vertices and edges in the model of vertex, edge, total and pseudototal coloring of graphs. We use a dynamic programming approach to derive polynomial-time algorithms for solving the above problems for trees. Then we generalize this approach to arbitrary graphs with bounded cyclomatic numbers and to their multicolorings.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 2; 361-376
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Equitable Colorings Of Corona Multiproducts Of Graphs
Autorzy:
Furmánczyk, Hanna
Kubale, Marek
Mkrtchyan, Vahan V.
Powiązania:
https://bibliotekanauki.pl/articles/31341573.pdf
Data publikacji:
2017-11-27
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
corona graph
equitable chromatic number
equitable coloring conjecture
equitable graph coloring
multiproduct of graphs
NP-completeness
polynomial algorithm
Opis:
A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the numbers of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G and denoted by χ=(G). It is known that the problem of computation of χ=(G) is NP-hard in general and remains so for corona graphs. In this paper we consider the same model of coloring in the case of corona multiproducts of graphs. In particular, we obtain some results regarding the equitable chromatic number for the l-corona product G ◦l H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs are mostly constructive in that they lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G. Moreover, we confirm the Equitable Coloring Conjecture for corona products of such graphs. This paper extends the results from [H. Furmánczyk, K. Kaliraj, M. Kubale and V.J. Vivin, Equitable coloring of corona products of graphs, Adv. Appl. Discrete Math. 11 (2013) 103–120].
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 4; 1079-1094
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Better polynomial algorithms for scheduling unit-length jobswith bipartite incompatibility graphs on uniform machines
Autorzy:
Pikies, T.
Kubale, Marek
Powiązania:
https://bibliotekanauki.pl/articles/201958.pdf
Data publikacji:
2019
Wydawca:
Polska Akademia Nauk. Czytelnia Czasopism PAN
Tematy:
approximation algorithm
graph coloring
incompatible job
polynomial algorithm
scheduling
uniform machine
unit-time jobs
algorytm aproksymacyjny
kolorowanie grafów
algorytm wielomianowy
planowanie
praca jednostkowa
Opis:
The goal of this paper is to explore and to provide tools for the investigation of the problems of unit-length scheduling of incompatible jobs on uniform machines. We present two new algorithms that are a significant improvement over the known algorithms. The first one is Algorithm 2 which is 2-approximate for the problem Qm|pj = 1, G = bisubquartic|Cmax. The second one is Algorithm 3 which is 4-approximate for the problem Qm|pj = 1, G = bisubquartic|ΣCj, where m ϵ {2, 3, 4}. The theory behind the proposed algorithms is based on the properties of 2-coloring with maximal coloring width, and on the properties of ideal machine, an abstract machine that we introduce in this paper.
Źródło:
Bulletin of the Polish Academy of Sciences. Technical Sciences; 2019, 67, 1; 31-36
0239-7528
Pojawia się w:
Bulletin of the Polish Academy of Sciences. Technical Sciences
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Assignment and sequencing of parts to autonomous workstations
Autorzy:
Lucertini, M.
Nicolo, F.
Smriglio, S.
Powiązania:
https://bibliotekanauki.pl/articles/206675.pdf
Data publikacji:
2000
Wydawca:
Polska Akademia Nauk. Instytut Badań Systemowych PAN
Tematy:
sterowanie porodukcją
teoria algorytmów
teoria systemów
złożoność obliczeniowa
bipartie matching
coordination mechanism
distributed algorithm
polynomial-time algorithm
Opis:
We present an optimization-based coordination protocol among autonomous workstations in a multiprocessor stage devoted to painting of the shutters in a furniture production process. The coordination aims to maximize the number of parallel operations executable at each machine cycle, while fulfilling constraints on the unique-copy tools. The mechanism is derived by a distributed implementation of a bipartite matching algorithm. The resulting procedure is shown to be compatible with the several autonomous decisions characterizing the process.
Źródło:
Control and Cybernetics; 2000, 29, 1; 221-236
0324-8569
Pojawia się w:
Control and Cybernetics
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Parallel Digraphs-building Computer Algorithm for Finding a Set of Characteristic Polynomial Realisations of Dynamic System
Autorzy:
Hryniów, K.
Markowski, K. A.
Powiązania:
https://bibliotekanauki.pl/articles/384585.pdf
Data publikacji:
2016
Wydawca:
Sieć Badawcza Łukasiewicz - Przemysłowy Instytut Automatyki i Pomiarów
Tematy:
dynamic system
GPGPU
characteristic polynomial
digraphs
algorithm
Opis:
This paper presents in-depth the parallel computer algorithm for the determination of characteristic polynomial realisations of dynamic system. The main differences between the depicted method and other state of- the-art solutions include finding not few realisations, but a whole set, and the fact that the found realisations are always minimal among all possible. As digraphsbuilding methods used in the algorithm are NP-complete or NP-hard problems, the algorithm is paralleled and GPGPU (General-Purpose computing on Graphics Processor Units) computation is proposed as the only feasible solution. The article describes in detail the proposed method, discusses it’s complexity, presents optimisation solutions and still open problems. The working algorithm is illustrated with a numerical example and compared to results of other known methods.
Źródło:
Journal of Automation Mobile Robotics and Intelligent Systems; 2016, 10, 3; 38-51
1897-8649
2080-2145
Pojawia się w:
Journal of Automation Mobile Robotics and Intelligent Systems
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A primal-infeasible interior point algorithm for linearly constrained convex programming
Autorzy:
Wang, Y.
Fei, P.
Powiązania:
https://bibliotekanauki.pl/articles/969664.pdf
Data publikacji:
2009
Wydawca:
Polska Akademia Nauk. Instytut Badań Systemowych PAN
Tematy:
linearly constrained convex programming
primal-infeasible interior point algorithm
polynomial complexity
Opis:
In this paper a primal-infeasible interior point algorithm is proposed for linearly constrained convex programming. A positive primal-infeasible dual-feasible point can be taken as the starting point of this algorithm in a large region. At each iterates it requires to solve approximately a nonlinear system. The polynomial complexity of the algorithm is obtained. It is shown that, after finite iterations a sufficiently good approximation to the optimal point is found, or there is no optimal point in a large region.
Źródło:
Control and Cybernetics; 2009, 38, 3; 687-704
0324-8569
Pojawia się w:
Control and Cybernetics
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Acoustical Assessment of Automotive Mufflers Using FEM, Neural Networks, and a Genetic Algorithm
Autorzy:
Chang, Y.-C.
Chiu, M.-C.
Wu, M.-R.
Powiązania:
https://bibliotekanauki.pl/articles/177901.pdf
Data publikacji:
2018
Wydawca:
Polska Akademia Nauk. Czytelnia Czasopism PAN
Tematy:
acoustics
finite element method
genetic algorithm
muffler optimization
polynomial neural network model
Opis:
In order to enhance the acoustical performance of a traditional straight-path automobile muffler, a multi-chamber muffler having reverse paths is presented. Here, the muffler is composed of two internally parallel/extended tubes and one internally extended outlet. In addition, to prevent noise transmission from the muffler’s casing, the muffler’s shell is also lined with sound absorbing material. Because the geometry of an automotive muffler is complicated, using an analytic method to predict a muffler’s acoustical performance is difficult; therefore, COMSOL, a finite element analysis software, is adopted to estimate the automotive muffler’s sound transmission loss. However, optimizing the shape of a complicated muffler using an optimizer linked to the Finite Element Method (FEM) is time-consuming. Therefore, in order to facilitate the muffler’s optimization, a simplified mathematical model used as an objective function (or fitness function) during the optimization process is presented. Here, the objective function can be established by using Artificial Neural Networks (ANNs) in conjunction with the muffler’s design parameters and related TLs (simulated by FEM). With this, the muffler’s optimization can proceed by linking the objective function to an optimizer, a Genetic Algorithm (GA). Consequently, the discharged muffler which is optimally shaped will improve the automotive exhaust noise.
Źródło:
Archives of Acoustics; 2018, 43, 3; 517-529
0137-5075
Pojawia się w:
Archives of Acoustics
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 21

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies