Temat: combinatorial optimization - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Solving a permutation problem by a fully polynomial-time approximation scheme
Autorzy:: Gawiejnowicz, Stanisław
Kurc, Wiesław
Pankowska, Lidia
Powiązania:: https://bibliotekanauki.pl/articles/729290.pdf
Data publikacji:: 2010
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: combinatorial optimization
discrete control theory
fully polynomial-time approximation scheme
Opis:: For a problem of optimal discrete control with a discrete control set composed of vertices of an n-dimensional permutohedron, a fully polynomial-time approximation scheme is proposed.
Źródło:: Discussiones Mathematicae, Differential Inclusions, Control and Optimization; 2010, 30, 2; 191-203
1509-9407
Pojawia się w:: Discussiones Mathematicae, Differential Inclusions, Control and Optimization
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: An Efficient Polynomial Time Approximation Scheme for the Vertex Cover P₃ Problem on Planar Graphs
Autorzy:: Tu, Jianhua
Shi, Yongtang
Powiązania:: https://bibliotekanauki.pl/articles/31343724.pdf
Data publikacji:: 2019-02-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: combinatorial optimization
vertex cover P3 problem
branch- width
planar graphs
EPTAS
Opis:: Given a graph G = (V,E), the task in the vertex cover P₃(VCP₃) problem is to find a minimum subset of vertices F ⊆ V such that every path of order 3 in G contains at least one vertex from F. The VCP₃ problem remains NP-hard even in planar graphs and has many applications in real world. In this paper, we give a dynamic-programming algorithm to solve the VCP₃ problem on graphs of bounded branchwidth. Using the dynamic programming algorithm and the Baker’s EPTAS framework for NP-hard problems, we present an efficient polynomial time approximation scheme (EPTAS) for the VCP₃ problem on planar graphs.
Źródło:: Discussiones Mathematicae Graph Theory; 2019, 39, 1; 55-65
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: New lower bounds on the weighted chromatic number of a graph
Autorzy:: Caramia, Massimiliano
Fiala, Jirí
Powiązania:: https://bibliotekanauki.pl/articles/744465.pdf
Data publikacji:: 2004
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: combinatorial analysis
computational analysis
optimization
Opis:: In this paper we present theoretical and algorithmic results for the computation of lower bounds on the chromatic number of a weighted graph. In particular, we study different ways of a possible improvement of the lower bound offered by a maximum weighted clique. Based on our findings we devise new algorithms and show their performance on random graphs.
Źródło:: Discussiones Mathematicae Graph Theory; 2004, 24, 2; 183-195
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja