Michał Małafiejski - Profil naukowy - MOST Wiedzy

Wyszukiwarka

Kontakt

Profesor nadzwyczajny ze stop. nauk. dr hab.

Katedra Algorytmów i Modelowania Systemów
Wydział Elektroniki, Telekomunikacji i Informatyki

Miejsce pracy Gmach Elektroniki Telekomunikacji i Informatyki pokój 224

Telefon (58) 347 10 64

Wybrane publikacje

  • The complexity of the L(p,q)-labeling problem for bipartite planar graphs of small degree

    W pracy pokazano, że problem L(p,q)-kolorowania przy użyciu ''t'' kolorów jest NP-zupełny nawet w wersji ograniczonej do grafów planarnych dwudzielnych małego stopnia, nawet dla stosunkowo niewielkich wartości ''t''. Jako wniosek z uzyskanych wyników stwierdzono, że problem L(2,1)-kolorowania grafów planarnych przy użyciu 4 kolorów jest NP-zupełny, a także że problem L(p,q)-kolorowania grafów o maksymalnym stopniu 4 jest NP-zupełny...
    • Pełny tekst w serwisie zewnętrznym
  • Cooperative mobile guards in grids

    Praca dotyczy problemu strzeżenia dwuwymiarowych krat ortogonalnych, przy założeniu, że obszar widoczności strażnika obejmuje jedną ulicę oraz wszystkie ulice ją przecinające. Rozważano wariant straży słabo współpracujących, w którym dodatkowo każdy strażnik musi widzieć przynajmniej jednego innego strażnika. Podano dowód NP-trudności problemu optymalizacyjnego w przypadku ogólnym, algorytm dokładny o złożoności O(n log n) dla...
    • Pełny tekst w serwisie zewnętrznym
  • Packing [1,Delta]-factors in graphs of small degree

    Rozważano problem znalezienia w grafie zadanej liczby k krawędziowo rozłącznych [1,Delta]-faktorów, gdzie Delta oznacza stopień grafu. Problem ten można rozwiązać w czasie liniowym dla k=2, jest on jednak NP-trudny dla każdego k>=3. Pokazano, że wariant minimalizacjny problemu dla k=2 jest NP-trudny dla grafów planarnych podkubicznych, jednak w ogólności istnieje algorytm (42 Delta - 30) / (35 Delta - 21) - aproksymacyjny.
    • Pełny tekst w serwisie zewnętrznym

Uzyskane stopnie/tytuły naukowe

wyświetlono 130 razy