Temat: circular-arc graphs - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: A Note on Longest Paths in Circular Arc Graphs
Autorzy:: Joos, Felix
Powiązania:: https://bibliotekanauki.pl/articles/31339425.pdf
Data publikacji:: 2015-08-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: circular arc graphs
longest paths intersection
Opis:: As observed by Rautenbach and Sereni [SIAM J. Discrete Math. 28 (2014) 335-341] there is a gap in the proof of the theorem of Balister et al. [Combin. Probab. Comput. 13 (2004) 311-317], which states that the intersection of all longest paths in a connected circular arc graph is nonempty. In this paper we close this gap.
Źródło:: Discussiones Mathematicae Graph Theory; 2015, 35, 3; 419-426
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

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
Opis:: 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.
Źródło:: Discussiones Mathematicae Graph Theory; 2004, 24, 1; 137-145
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja