|
Title:
|
DYNAMIC CONTROL NODES IN GRAPHS |
|
Author(s):
|
Ricardo Contreras Apablaza , Julio Godoy |
|
ISBN:
|
978-972-8924-62-1 |
|
Editors:
|
Hans Weghorn and Ajith P. Abraham |
|
Year:
|
2008 |
|
Edition:
|
Single |
|
Keywords:
|
Ptolemaic graphs, control nodes, tree-covering, laminar structures, chordal graphs |
|
Type:
|
Short Paper |
|
First Page:
|
205 |
|
Last Page:
|
209 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
Coloring problem, in graph theory, is known to be NP-Hard for the chromatic number and NP-Complete for the
corresponding decision problem. However, for a clique, it is also known that the chromatic number equals the size of that
clique. We use this principle and propose a control algorithm, based on a laminar structure, that performs a control over
certain graphs families in O(|V| + |E|) time. For an illustrating and corroborating purpose we based our study on a
classical chase problem. |
|
|
|
|
|
|
