Marek Kubale - Publikacje - MOST Wiedzy

Wyszukiwarka

Filtry

wszystkich: 125

  • Kategoria
  • Rok
  • Opcje

wyczyść Filtry wybranego katalogu niedostępne

Katalog Publikacji

Rok 2024
  • Equitable colorings of some variation of corona products of cubic graphs
    Publikacja

    - Archives of Control Sciences - Rok 2024

    The 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.

    Pełny tekst do pobrania w portalu

  • Potyczki algorytmiczne, czyli Alicja i Bogdan w nowych sytuacjach
    Publikacja

    W kolejnym odcinku serii z Alicją i Bogdanem najpierw ilustrujemy problem dominowania w grafach (kratowych): klasyczny i rzymski. Następnie ilustrujemy znany fakt, że zachłanność nie zawsze się opłaca. Pokażemy mianowicie, że algorytmy zachłanne nie gwarantują uzyskania rozwiązania optymalnego, nawet wówczas gdy problem da się rozwiązać w czasie wielomianowym.

    Pełny tekst do pobrania w portalu

  • Teoria grafów wczoraj i dziś
    Publikacja

    - Rok 2024

    W pracy naszkicowano kamienie milowe teorii grafów poczynając od pierwszego artykułu Eulera na temat mostów w Królewcu z połowy 18. wieku. Następnie opisano słynny problem 4 barw i jego wariacje. Pracę kończy charakterystyka najnowszych wyzwań teorii grafów.

    Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2023
Rok 2022
Rok 2021
Rok 2020
  • A note on polynomial algorithm for cost coloring of bipartite graphs with Δ ≤ 4

    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(n^2) time. This extends Jansen’s result [K.Jansen,The optimum cost chromatic partition problem, in:...

    Pełny tekst do pobrania w portalu

  • Chromatic cost coloring of weighted bipartite graphs

    Given a graph G and a sequence of color costs C, the Cost Coloring optimization problem consists in finding a coloring of G with the smallest total cost with respect to C. We present an analysis of this problem with respect to weighted bipartite graphs. We specify for which finite sequences of color costs the problem is NP-hard and we present an exact polynomial algorithm for the other finite sequences. These results are then extended...

    Pełny tekst do pobrania w serwisie zewnętrznym

Rok 2019
Rok 2018
Rok 2017
Rok 2016
Rok 2015

wyświetlono 6076 razy