A simple linear algorithm for the connected domination problem in circular-arc graphs

Szczegóły
Opis

Tytuł:: A simple linear algorithm for the connected domination problem in circular-arc graphs
Autorzy:: Hung, Ruo-Wei
Chang, Maw-Shang
Powiązania:: https://bibliotekanauki.pl/articles/744451.pdf
Data publikacji:: 2004
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: graph algorithms
circular-arc graphs
connected dominating set
shortest path
Źródło:: Discussiones Mathematicae Graph Theory; 2004, 24, 1; 137-145
2083-5892
Język:: angielski
Prawa:: Wszystkie prawa zastrzeżone. Swoboda użytkownika ograniczona do ustawowego zakresu dozwolonego użytku
Dostawca treści:: Biblioteka Nauki
: Artykuł

Przejdź do źródła

A connected dominating set of a graph G = (V,E) is a subset of vertices CD ⊆ V such that every vertex not in CD is adjacent to at least one vertex in CD, and the subgraph induced by CD is connected. We show that, given an arc family F with endpoints sorted, a minimum-cardinality connected dominating set of the circular-arc graph constructed from F can be computed in O(|F|) time.

Informacja

Powiązane pozycje