Temat: polynomial-time algorithm - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Finding Dominating Induced Matchings in P₉-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 P₇-free graphs and in polynomial time for P₈-free graphs. In this paper, we solve it in polynomial time for P₉-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ł

Skocz do pozycji: 2.

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ł

Skocz do pozycji: 3.

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ł

Skocz do pozycji: 4.

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|p_j = 1, G = bisubquartic|C_max. The second one is Algorithm 3 which is 4-approximate for the problem Qm|p_j = 1, G = bisubquartic|ΣC_j, 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ł

Informacja