Michael R. Fellows

Michael R. Fellows

Auto-generated profile, based on publicly available information

Michael R. Fellows

University of Bergen Norway

Research Focus & Metrics

Academic Career Length

40Years (1987-Present)

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

Representative Publications

View All Publications
1 December 2009 in Journal of Computer and System Sciences
Verified
Journal Article
Closed access
HBHans L. Bodlaender
Hans L. Bodlaender
RDRodney G. Downey
Rodney G. Downey
MFMichael R. Fellows
Michael R. Fellows
DHDanny Hermelin
Danny Hermelin

1 April 1995 in Theoretical Computer Science
Verified
Journal Article
Closed access
RDRod G. Downey
Rod G. Downey
MFMichael R. Fellows
Michael R. Fellows

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 May 2004 in Journal of the ACM
Verified
Journal Article
Open access
PDF file
JAJochen Alber
Jochen Alber
MFMichael R. Fellows
Michael R. Fellows
RNRolf Niedermeier
Rolf Niedermeier
Dealing with the NP-complete Dominating Set problem on graphs, we demonstrate the power of data reduction by preprocessing from a theoretical as well as a practical side. In particular, we prove that Dominating Set restricted to planar graphs has a so-called problem kernel of linear size, achieved by two simple and easy-to-implement reduction rules. Moreover, having implemented our reduction rules, first experiments indicate the impressive practical potential of these rules. Thus, this work seems to open up a new and prospective way how to cope with one of the most important problems in graph theory and combinatorial optimization.

1 September 2005 in Information and Computation
Verified
Journal Article
Closed access
JCJianer Chen
Jianer Chen
BCBenny Chor
Benny Chor
MFMike Fellows
Mike Fellows
XHXiuzhen Huang
Xiuzhen Huang
DJDavid Juedes
David Juedes
GXGe Xia
Ge Xia

1 June 1988 in Journal of the ACM
Verified
Journal Article
Open access
MFMichael R. Fellows
Michael R. Fellows
MLMichael A. Langston
Michael A. Langston
Recent advances in graph theory and graph algorithms dramatically alter the traditional view of concrete complexity theory, in which a decision problem is generally shown to be in P by producing an efficient algorithm to solve an optimization version of the problem. Nonconstructive tools are now available for classifying problems as decidable in polynomial time by guaranteeing only theexistenceof polynomial-timedecisionalgorithms. In this paper these new methods are employed to prove membership in P for a number of problems whose complexities are not otherwise known. Powerful consequences of these techniques are pointed out and their utility is illustrated. A type of partially ordered set that supports this general approach is defined and explored.