Wyniki wyszukiwania dla: PERFECT GRAPHS

• Some variations of perfect graphs

  Publikacja

  • M. Dettlaff
  • M. Lemańska
  • G. Semanišin
  • R. Zuazua

  - Discussiones Mathematicae Graph Theory - Rok 2016

  We consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) =γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k -path vertex cover number and the distance (k−1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k≥2. Moreover, we provide a complete characterisation of (ψ2−γ1)-perfect graphs describing the set of its forbidden induced subgraphs and providing...

  Pełny tekst do pobrania w portalu

• Perfect Beat

  Czasopisma

  ISSN: 1038-2909 , eISSN: 1836-0343

• GRAPHS AND COMBINATORICS

  Czasopisma

  ISSN: 0911-0119 , eISSN: 1435-5914

• Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.

  Publikacja

  • H. Furmańczyk
  • A. Kosowski
  • P. Żyliński

  - Rok 2008

  W pracy rozważono problem kolorowania grafów mieszanych, opisujący zagadnienie szeregowania zadań, w którym zależności czasowe zadań mają charakter częściowego porządku lub wzajemnego wykluczania. Dla przypadku, w którym graf zależności jest szeregowo-równoległy, podano algorytm rozwiązujący problem optymalnie w czasie $O(n^3.376 * log n)$.

  Pełny tekst do pobrania w serwisie zewnętrznym

• Discussiones Mathematicae Graph Theory

  Czasopisma

  ISSN: 1234-3099 , eISSN: 2083-5892

• Connection graphs

  Publikacja

  • P. Bartłomiejczyk

  - FUNDAMENTA MATHEMATICAE - Rok 2006

  Pełny tekst do pobrania w serwisie zewnętrznym

• Some variants of perfect graphs related to the matching number, the vertex cover and the weakly connected domination number

  Publikacja

  • S. Bermudo
  • M. Dettlaff
  • M. Lemańska

  - DISCRETE APPLIED MATHEMATICS - Rok 2021

  Given two types of graph theoretical parameters ρ and σ, we say that a graph G is (σ, ρ)- perfect if σ(H) = ρ(H) for every non-trivial connected induced subgraph H of G. In this work we characterize (γw, τ )-perfect graphs, (γw, α′)-perfect graphs, and (α′, τ )-perfect graphs, where γw(G), τ (G) and α′(G) denote the weakly connected domination number, the vertex cover number and the matching number of G, respectively. Moreover,...

  Pełny tekst do pobrania w serwisie zewnętrznym

• Rank Coloring of Graphs.

  Publikacja

  • D. Dereniowski

  - Rok 2004

  Rozdział jest poświęcony uporządkowanemu kolorowaniu grafów. Przedstawiono jego podstawowe własności oraz zastosowania praktyczne.

• Circular colorings of graphs.

  Publikacja

  • A. Nadolski

  - Rok 2004

  Rozdział poświęcony jest cyrkularnemu modelowi kolorowania krawędzi. Rozważana jest zarówno wersja wierzchołkowa i krawędziowa. Szczególny nacisk położono na złożoność obliczeniową i zastosowania dla omawianych modeli kolorowania.

• Harmonions Coloring of Graphs.

  Publikacja

  • M. Kubale

  - Rok 2004

  Problem kolorowania grafów jest motywowany radionawigacją lotniczą, kompresją obrazów i in. W rozdziale podano podstawowe fakty dotyczące tego modelu kolorowania, a wsród nich dolne i górne oszacowania na liczbę harmoniczną i algorytm o złożoności 0 (mm3) dający bardzo dobre pokolorowania przybliżone.