Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Optimal edge ranking of complete bipartite graphs in polynomial time

100%

Hung R.-W.

Discussiones Mathematicae Graph Theory

2006

tom 26

nr 1

149-159

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.

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

63%

Hung R.-W., Chang M.-S.

Discussiones Mathematicae Graph Theory

2004

tom 24

nr 1

137-145

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.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Hung R.-W.

1 Chang M.-S.

1 2006

1 2004

Wyniki wyszukiwania

Optimal edge ranking of complete bipartite graphs in polynomial time

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