Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Optimal edge ranking of complete bipartite graphs in polynomial time

Ruo-Wei Hung — 2006

Discussiones Mathematicae Graph Theory

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...

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

Ruo-Wei Hung;  Maw-Shang Chang — 2004

Discussiones Mathematicae Graph Theory

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.

Page 1

Download Results (CSV)