Frances  Rosamond

Prof. Dr. Frances Rosamond

Department of Informatics, University of Bergen, Postboks 7803, 5020 Bergen, Norway

Research Focus & Metrics

Academic Career Length

25Years (2002-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 January 2009 in Theoretical Computer Science
Verified
Journal Article
Closed access
MFMichael R. Fellows
Michael R. Fellows
DHDanny Hermelin
Danny Hermelin
Frances  RosamondFrances Rosamond
Frances Rosamond
SVStéphane Vialette
Stéphane Vialette

1 February 2011 in Information and Computation
Verified
Journal Article
Closed access
MFMichael R. Fellows
Michael R. Fellows
FFFedor V. Fomin
Fedor V. Fomin
DLDaniel Lokshtanov
Daniel Lokshtanov
Frances  RosamondFrances Rosamond
Frances Rosamond
SSSaket Saurabh
Saket Saurabh
CTCarsten Thomassen
Carsten Thomassen

1 January 2009 in SIAM Journal on Discrete Mathematics
Verified
Journal Article
Closed access
MFMichael R. Fellows
Michael R. Fellows
Frances  RosamondFrances Rosamond
Frances Rosamond
URUdi Rotics
Udi Rotics
SSStefan Szeider
Stefan Szeider
Clique-width is a graph parameter that measures in a certain sense the complexity of a graph. Hard graph problems (e.g., problems expressible in monadic second-order logic with second-order quantification on vertex sets, which includes NP-hard problems such as 3-colorability) can be solved in polynomial time for graphs of bounded clique-width. We show that the clique-width of a given graph cannot be absolutely approximated in polynomial time unless $P = NP$. We also show that, given a graph G and an integer k, deciding whether the clique-width of G is at most k is NP-complete. This solves a problem that has been open since the introduction of clique-width in the early 1990s.

1 April 2013 in European Journal of Combinatorics
Verified
Journal Article
Closed access
MFMichael R. Fellows
Michael R. Fellows
BJBart M.P. Jansen
Bart M.P. Jansen
Frances  RosamondFrances Rosamond
Frances Rosamond

29 January 2009 in Theory of Computing Systems
Verified
Journal Article
Closed access
PDF file
MFMichael Fellows
Michael Fellows
DLDaniel Lokshtanov
Daniel Lokshtanov
NMNeeldhara Misra
Neeldhara Misra
MMMatthias Mnich
Matthias Mnich
Frances  RosamondFrances Rosamond
Frances Rosamond
SSSaket Saurabh
Saket Saurabh

1 January 2008
Verified
Book Chapter
Closed access
PDF file
MFMichael R. Fellows
Michael R. Fellows
DLDaniel Lokshtanov
Daniel Lokshtanov
NMNeeldhara Misra
Neeldhara Misra
Frances  RosamondFrances Rosamond
Frances Rosamond
SSSaket Saurabh
Saket Saurabh