Displaying similar documents to “Planar Graphs”

The arc-width of a graph.

Barát, János, Hajnal, Péter (2001)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

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

Ruo-Wei Hung, Maw-Shang Chang (2004)

Discussiones Mathematicae Graph Theory

Similarity:

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.

Bounds of graph parameters for global constraints

Nicolas Beldiceanu, Thierry Petit, Guillaume Rochart (2006)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

This article presents a basic scheme for deriving systematically a filtering algorithm from the graph properties based representation of global constraints. This scheme is based on the bounds of the graph parameters used in the description of a global constraint. The article provides bounds for the most common used graph parameters.