Publikacje
Filtry
wszystkich: 46
Katalog Publikacji
-
T-colorings, divisibility and circular chromatic number
PublikacjaLet T be a T-set, i.e., a finite set of nonnegative integers satisfying 0 ∈ T, and G be a graph. In the paper we study relations between the T-edge spans espT (G) and espd⊙T (G), where d is a positive integer and d ⊙ T = {0 ≤ t ≤ d (max T + 1): d |t ⇒ t/d ∈ T} . We show that espd⊙T (G) = d espT (G) − r, where r, 0 ≤ r ≤ d − 1, is an integer that depends on T and G. Next we focus on the case T = {0} and show that espd⊙{0} (G) =...
-
Edge coloring of graphs of signed class 1 and 2
PublikacjaRecently, Behr (2020) introduced a notion of the chromatic index of signed graphs and proved that for every signed graph (G, σ) it holds that ∆(G) ≤ χ′(G,σ) ≤ ∆(G) + 1, where ∆(G) is the maximum degree of G and χ′ denotes its chromatic index. In general, the chromatic index of (G, σ) depends on both the underlying graph G and the signature σ. In the paper we study graphs G for which χ′(G, σ) does not depend on σ. To this aim we...
-
Potyczki algorytmiczne, czyli Alicja i Bogdan w nowych sytuacjach. 3. Alicja i Bogdan remontują mieszkanie.
PublikacjaPoniższe zagadki nawiązują z jednej strony do problemu kafelkowania płaszczyzny, który jest nierozstrzygalny, z drugiej do problemu rozkroju wstęgi, który jest NP-trudny. Jednakże przypadki szczególne, które tu rozważamy, nie są tak trudne i mogą być rozwiązane za pomocą algorytmów działających w czasie wielomianowym.
-
O problemie przydziału częstotliwości, kontrastowym kolorowaniu grafów i częściowych k-drzewach
PublikacjaNiniejszy artykuł poświęcony jest złożoności obliczeniowej problemu przydziału częstotliwości. Zawiera dowód tego, że jest on NP-trudny nawet dla grafów interferencji, będących grafami dwudzielnymi, oraz wielomianowy algorytm rozwiązujący ten problem dla grafów interferencji, będących częściowymi k-drzewami.
-
T-SL, T-SLF i T-DSATUR - nowe heurystyki dla problemu przydziału częstotliwości
PublikacjaNiniejszy artykuł poświęcony został algorytmom T-SL, T-SLF i T-DSATUR - nowym heurystykom dla problemu przydziału częstotliwości. Zawiera opis algorytmów, omówienie ich teoretycznych własności oraz wyniki testów komputerowych, którym zostały poddane.
-
Algorytmy przybliżone dla wybranych problemów równoległego przydziału zasobów
PublikacjaArtykuł poświęcony jest zachłannym algorytmom przybliżonym dla problemu szeregowania zadań w systemach równoległych z zadaniami dedykowanymi.