19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Distinguishing Trees in Linear Time
Presented by Dr. Antoni LOZANO
Type: Oral presentation
Track: Algorithmic Graph Theory
Content
A graph is said to be d-distinguishable if there exists a
d-labeling of its vertices which is only preserved by the identity map. The distinguishing number of a graph G is the smallest number d for which G is d-distinguishable. We show that the distinguishing number of trees and forests can be computed in linear time, improving the previously known O(n log n) time algorithm.
Place
Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled
Co-authors
- Dr. Merce MORA Universitat Politècnica de Catalunya
- Dr. Carlos SEARA Universitat Politècnica de Catalunya