O problemie przydziału częstotliwości, kontrastowym kolorowaniu grafów i częściowych k-drzewach

Krzysztof Giaro; Robert Janczewski

O problemie przydziału częstotliwości, kontrastowym kolorowaniu grafów i częściowych k-drzewach

Abstract

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

Authors (2)

Cite as

Full text

full text is not available in portal

Keywords

Details

Category:: Articles
Type:: artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
Published in:: Zeszyty Naukowe Politechniki Śląskiej. Automatyka pages 67 - 73,
ISSN: 0434-0760
Language:: Polish
Publication year:: 2002
Bibliographic description:: Giaro K., Janczewski R.: O problemie przydziału częstotliwości, kontrastowym kolorowaniu grafów i częściowych k-drzewach// Zeszyty Naukowe Politechniki Śląskiej. Automatyka. -., nr. 1596, z. 136 (2002), s.67-73
Verified by:: Gdańsk University of Technology