Now showing items 1-3 of 3
A polynomial-time solvable case for the NP-hard problem Cutwidth
(The University of Bergen, 2014-06-02)
The Cutwidth problem is a notoriously hard problem, and its complexity is open on several interesting graph classes. Motivated by this fact we investigate the problem on superfragile graphs, a graph class on which the ...
Independent Set on P5-free graphs, an empirical study
(The University of Bergen, 2015-11-20)
We implement the recent polynomial time algorithm for the independent set problem on P5-free graphs, and study the performance of this algorithm on graphs of size up to 50. Our empirical results show that the algorithm ...
Computation of Treespan. A Generalization of Bandwidth to Treelike Structures
(The University of Bergen, 2012-06-14)
Motivated by a search game, Fomin, Heggernes and Telle [Algorithmica, 2005] defined the graph parameter treespan, a generalization of the well studied parameter bandwidth. Treespan is the maximum number of appearances ...