Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 6

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  graph algorithms
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Factoring directed graphs with respect to the cardinal product in polynomial time

100%
Imrich W., Klöckl W.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 3
593-601
EN
By a result of McKenzie [4] finite directed graphs that satisfy certain connectivity and thinness conditions have the unique prime factorization property with respect to the cardinal product. We show that this property still holds under weaker connectivity and stronger thinness conditions. Furthermore, for such graphs the factorization can be determined in polynomial time.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Stable sets for $(P₆,K_{2,3})$-free graphs

100%
Mosca R.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 3
387-401
EN
The Maximum Stable Set (MS) problem is a well known NP-hard problem. However different graph classes for which MS can be efficiently solved have been detected and the augmenting graph technique seems to be a fruitful tool to this aim. In this paper we apply a recent characterization of minimal augmenting graphs [22] to prove that MS can be solved for $(P₆,K_{2,3})$-free graphs in polynomial time, extending some known results.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

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

100%
Hung R.-W., Chang M.-S.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 1
137-145
EN
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.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Factoring directed graphs with respect to the cardinal product in polynomial time II

100%
Imrich W., Klöckl W.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 3
461-474
EN
By a result of McKenzie [7] all finite directed graphs that satisfy certain connectivity conditions have unique prime factorizations with respect to the cardinal product. McKenzie does not provide an algorithm, and even up to now no polynomial algorithm that factors all graphs satisfying McKenzie's conditions is known. Only partial results [1,3,5] have been published, all of which depend on certain thinness conditions of the graphs to be factored. In this paper we weaken the thinness conditions and thus significantly extend the class of graphs for which the prime factorization can be found in polynomial time.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Colouring graphs with prescribed induced cycle lengths

88%
Randerath B., Schiermeyer I.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 2
267-281
EN
In this paper we study the chromatic number of graphs with two prescribed induced cycle lengths. It is due to Sumner that triangle-free and P₅-free or triangle-free, P₆-free and C₆-free graphs are 3-colourable. A canonical extension of these graph classes is $𝓖^I(4,5)$, the class of all graphs whose induced cycle lengths are 4 or 5. Our main result states that all graphs of $𝓖^I(4,5)$ are 3-colourable. Moreover, we present polynomial time algorithms to 3-colour all triangle-free graphs G of this kind, i.e., we have polynomial time algorithms to 3-colour every $G ∈ 𝓖^I(n₁,n₂)$ with n₁,n₂ ≥ 4 (see Table 1). Furthermore, we consider the related problem of finding a χ-binding function for the class $𝓖^I(n₁,n₂)$. Here we obtain the surprising result that there exists no linear χ-binding function for $𝓖^I(3,4)$.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Optimal edge ranking of complete bipartite graphs in polynomial time

88%
Hung R.-W.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 1
149-159
EN
An edge ranking of a graph is a labeling of edges using positive integers such that all paths connecting two edges with the same label visit an intermediate edge with a higher label. An edge ranking of a graph is optimal if the number of labels used is minimum among all edge rankings. As the problem of finding optimal edge rankings for general graphs is NP-hard [12], it is interesting to concentrate on special classes of graphs and find optimal edge rankings for them efficiently. Apart from trees and complete graphs, little has been known about special classes of graphs for which the problem can be solved in polynomial time. In this paper, we present a polynomial-time algorithm to find an optimal edge ranking for a complete bipartite graph by using the dynamic programming strategy.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.