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

MawShang Chang | Zendy; Ruo-Wei Hung | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

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

Author(s) -

MawShang Chang,

Ruo-Wei Hung

Publication year - 2004

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.1220

Subject(s) - combinatorics , mathematics , dominating set , vertex (graph theory) , induced subgraph , graph , connectivity , arc (geometry) , distance hereditary graph , discrete mathematics , line graph , graph power , geometry

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(jFj) time.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research