Michael Fellows | Academic Influence

Michael Fellows's AcademicInfluence.com Rankings

Michael Fellows

Computer Science

#1590

World Rank

#1645

Historical Rank

#777

USA Rank

Database

#2777

World Rank

#2901

Historical Rank

#566

USA Rank

computer-science Degrees

Download Badge

Computer Science

Michael Fellows's Degrees

PhD Computer Science University of California, Berkeley
Bachelors Mathematics University of California, Berkeley

Similar Degrees You Can Earn

Why Is Michael Fellows Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Michael Ralph Fellows AC HFRSNZ MAE is a computer scientist and the Elite Professor of Computer Science in the Department of Informatics at the University of Bergen, Norway as of January 2016. Biography Fellows received his BA in Mathematics from Sonoma State University, and at the University of California, San Diego his M.A. in Mathematics in 1982 and in 1985 his Ph.D. in Computer Science with the dissertation Encoding Graphs in Graphs.

(See a Problem?)

Michael Fellows's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Parameterized Complexity (1998) (3170)
Fundamentals of Parameterized Complexity (2013) (1168)
Fixed-Parameter Tractability and Completeness II: On Completeness for W[1] (1995) (572)
On problems without polynomial kernels (2009) (524)
Fixed-Parameter Tractability and Completeness I: Basic Results (1995) (428)
On the parameterized complexity of multiple-interval graph problems (2009) (314)
Fixed Parameter Tractability and Completeness (1992) (290)
Nonconstructive tools for proving polynomial-time decidability (1988) (249)
Polynomial-time data reduction for dominating set (2002) (238)
Two Strikes Against Perfect Phylogeny (1992) (229)
Tight lower bounds for certain parameterized NP-hard problems (2004) (214)
Parameterized complexity: A framework for systematically confronting computational intractability (1997) (197)
On search decision and the efficiency of polynomial-time algorithms (1989) (187)
Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments (2004) (175)
Parameterized Computational Feasibility (1995) (173)
Fixed-Parameter Tractability and Completeness IV: On Completeness for W[P] and PSPACE Analogues (1995) (161)
An Improved Fixed-Parameter Algorithm for Vertex Cover (1998) (157)
An O(2O(k)n3) FPT Algorithm for the Undirected Feedback Vertex Set Problem (2005) (129)
On the Complexity of Some Colorful Problems Parameterized by Treewidth (2007) (128)
Computer Science Unplugged: off-line activities and games for all ages (1998) (125)
Graph Layout Problems Parameterized by Vertex Cover (2008) (124)
Cutting Up is Hard to Do: the Parameterized Complexity of k-Cut and Related Problems (2003) (123)
Linear Kernels in Linear Time, or How to Save k Colors in O(n2) Steps (2004) (119)
Advice Classes of Parameterized Tractability (1997) (119)
Crown Structures for Vertex Cover Kernelization (2007) (118)
An analogue of the Myhill-Nerode theorem and its use in computing finite-basis characterizations (1989) (117)
Fixed-parameter intractability (1992) (114)
Parameterized complexity analysis in computational biology (1995) (112)
On Well-Partial-Order Theory and its Application to Combinatorial Problems of VLSI Design (1989) (107)
Clique-Width is NP-Complete (2009) (103)
The Parameterized Complexity of Sequence Alignment and Consensus (1994) (100)
Nonconstructive Advances in Polynomial-Time Complexity (1987) (100)
Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity (2013) (98)
On the parameterized complexity of short computation and factorization (1997) (95)
Finite automata, bounded treewidth, and well-quasiordering (1991) (95)
The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number (2007) (92)
Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (1994) (92)
Refined Search Tree Technique for DOMINATING SET on Planar Graphs (2001) (91)
The Parametrized Complexity of Some Fundamental Problems in Coding Theory (1999) (90)
Graph-based data clustering with overlaps (2009) (88)
Blow-Ups, Win/Win's, and Crown Rules: Some New Directions in FPT (2003) (87)
On complexity of lobbying in multiple referenda (2006) (85)
FPT is P-Time Extremal Structure I (2005) (79)
Fixed-parameter tractability and completeness III: some structural aspects of the W hierarchy (1993) (75)
On the Parameterized Complexity of Layered Graph Drawing (2001) (74)
Clique-width minimization is NP-hard (2006) (74)
Upper and lower bounds for finding connected motifs in vertex-colored graphs (2011) (73)
Parameterized Approximation Problems (2006) (73)
Fixed-parameter algorithms for Kemeny rankings (2009) (72)
On Problems without Polynomial Kernels (Extended Abstract) (2008) (71)
Computer Science Unplugged - an enrichment and extension programme for primary-aged children (2002) (69)
Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing (1992) (69)
Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs (2007) (68)
Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems (2008) (67)
The Parameterized Complexity of Relational Database Queries and an Improved Characterization of W[1] (1996) (67)
Algebraic Constructions of Efficient Broadcast Networks (1991) (66)
The complexity of induced minors and related problems (1995) (66)
Finding k Disjoint Triangles in an Arbitrary Graph (2004) (64)
Beyond NP-completeness for problems of bounded width (extended abstract): hardness for the W hierarchy (1994) (63)
Greedy Localization, Iterative Compression, Modeled Crown Reductions: New FPT Techniques, an Improved Algorithm for Set Splitting, and a Novel 2k Kernelization for Vertex Cover (2004) (63)
The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel (2006) (63)
On the complexity and combinatorics of covering finite complexes (1991) (61)
Local Search: Is Brute-Force Avoidable? (2009) (60)
Parameterized approximation via fidelity preserving transformations (2012) (57)
Self-witnessing polynomial-time complexity and prime factorization (1992) (54)
Combinatorial Cryptosystems Galore! (53)
Coordinatized Kernels and Catalytic Reductions: An Improved FPT Algorithm for Max Leaf Spanning Tree and Other Problems (2000) (53)
CS Unplugged: An enrichment and extension programme for primary-aged students (2015) (53)
DNA Physical Mapping: Three Ways Difficult (1993) (53)
Parameterized Algorithmics for Finding Connected Motifs in Biological Networks (2011) (52)
Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology (2009) (52)
An improved fixed parameter tractable algorithm for vertex cover (1999) (51)
Parameterized approximation of dominating set problems (2008) (51)
W[2]-hardness of precedence constrained K-processor scheduling (1995) (51)
Fixed-Parameter Complexity and Cryptography (1993) (51)
Analogs & duals of the MAST problem for sequences & trees (2003) (50)
The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs (2000) (50)
Parameterized Complexity: The Main Ideas and Connections to Practical Computing (2000) (50)
Parameterized learning complexity (1993) (50)
Efficient Parameterized Preprocessing for Cluster Editing (2007) (49)
Transversals of Vertex Partitions in Graphs (1990) (49)
Satisfying more than half of a system of linear equations over GF(2): A multivariate approach (2014) (48)
Fixed-Parameter Algorithms for Kemeny Scores (2008) (48)
Perfect domination (1991) (48)
Parameterized Complexity: The Main Ideas and Some Research Frontiers (2009) (47)
Control complexity in Bucklin and fallback voting: A theoretical analysis (2015) (47)
Parameterized Algorithms and Hardness Results for Some Graph Motif Problems (2008) (45)
Open Problems in Parameterized and Exact Computation - IWPEC 2006 (2006) (44)
The Dominating Set Problem Is Fixed Parameter Tractable for Graphs of Bounded Genus (2002) (44)
On The Parameterized Intractability Of Motif Search Problems* (2002) (44)
Large Planar Graphs with Given Diameter and Maximum Degree (1995) (44)
On the Structure of Parameterized Problems in NP (1995) (43)
Parameterized Circuit Complexity and the W Hierarchy (1998) (43)
Fixed-Parameter Intractability II (Extended Abstract) (1993) (43)
On the Multiple Gene Duplication Problem (1998) (43)
NONBLOCKER: Parameterized Algorithmics for minimum dominating set (2006) (43)
On search, decision, and the efficiency of polynomial-time algorithms (1994) (41)
Tractable Parameterizations for the Minimum Linear Arrangement Problem (2013) (41)
Efficient Data Reduction for DOMINATING SET: A Linear Problem Kernel for the Planar Case (2002) (41)
A Fixed-Parameter Approach to 2-Layer Planarization (2001) (41)
The Basic Definitions (2013) (40)
Computational Tractability: The View From Mars (1999) (40)
On the parametric complexity of schedules to minimize tardy tasks (2003) (39)
On the Parameterized Intractability of CLOSEST SUBSTRINGsize and Related Problems (2002) (38)
The Lost Continent of Polynomial Time: Preprocessing and Kernelization (2006) (38)
Small Diameter Symmetric Networks from Linear Groups (1992) (37)
The Private Neighbor Cube (1994) (36)
The parameterized complexity of some minimum label problems (2009) (35)
Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory (2019) (32)
A generalization of Nemhauser and Trotterʼs local optimization theorem (2009) (32)
New Directions and New Challenges in Algorithm Design and Complexity, Parameterized (2003) (31)
On computing graph minor obstruction sets (2000) (31)
Threshold Dominating Sets and an Improved Characterization of W[2] (1998) (31)
On the complexity of fixed parameter problems (1989) (30)
The complexity of irredundant sets parameterized by size (2000) (30)
Parameterizing by the Number of Numbers (2010) (30)
Connected Coloring Completion for General Graphs: Algorithms and Complexity (2007) (29)
An FPT Algorithm for Set Splitting (2003) (29)
Descriptive complexity and the W hierarchy (1996) (29)
Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average (2011) (29)
Layout permutation problems and well-partially-ordered sets (1988) (27)
Data Reduction and Problem Kernels (Dagstuhl Seminar 12241) (2012) (27)
Control complexity in Bucklin and fallback voting: An experimental analysis (2015) (26)
Facility location problems: A parameterized view (2008) (26)
Analogs and Duals of the MAST Problem for Sequences and Trees (1998) (25)
Forbidden minors to graphs with small feedback sets (2001) (23)
Clustering with partial information (2008) (23)
Parameterized complexity of firefighting (2014) (23)
Polynomial-time self-reducibility: theoretical motivations and practical results ∗ (1989) (22)
What Makes Equitable Connected Partition Easy (2009) (22)
Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems (2004) (21)
Derivation of algorithms for cutwidth and related graph layout parameters (2002) (21)
How similarity helps to efficiently compute Kemeny rankings (2009) (21)
Quadratic Kernelization for Convex Recoloring of Trees (2007) (21)
Distortion is Fixed Parameter Tractable (2009) (21)
Explaining cryptographic systems (2003) (21)
The Complexity of Polynomial-Time Approximation (2007) (21)
A Simple Linear-Time Algorithm for Finding Path-Decompositions of Small Width (1994) (20)
Parameterized Complexity of Stabbing Rectangles and Squares in the Plane (2009) (20)
A Linear Kernel for Co-Path/Cycle Packing (2010) (20)
Kid Krypto (1992) (19)
Well Quasi Orders in Subclasses of Bounded Treewidth Graphs and Their Algorithmic Applications (2012) (19)
Dynamic Dominating Set and Turbo-Charging Greedy Heuristics (2014) (19)
Constraint Satisfaction Problems: Convexity Makes AllDifferent Constraints Tractable (2011) (19)
A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second Order Ideals (1997) (19)
A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems (2009) (19)
What Is Known About Vertex Cover Kernelization? (2018) (19)
The Computer Journal Special Issue on Parameterized Complexity: Foreword by the Guest Editors (2008) (18)
Leaf Powers and Their Properties: Using the Trees (2008) (17)
Fast Self-Reduction Algorithms for Combinatorical Problems of VLSI-Design (1988) (17)
On the parameterized complexity of dynamic problems (2015) (17)
Obstructions to Within a Few Vertices or Edges of Acyclic (1995) (17)
Parameterized control complexity in bucklin voting and in fallback voting (2010) (16)
On Finding Short Resolution Refutations and Small Unsatisfiable Subsets (2004) (16)
Control Complexity in Bucklin and Fallback Voting (2011) (15)
The Parameterized Complexity of Abduction (2012) (15)
Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (2013) (14)
Proving NP-hardness for clique-width II: non-approximability of clique-width (2005) (14)
Computer science and mathematics in the elementary schools (1990) (14)
Myhill–Nerode Methods for Hypergraphs (2012) (14)
Well Quasi Orders in Subclasses of Bounded Treewidth Graphs and Their Algorithmic Applications (2009) (14)
Fast search algorithms for layout permutation problems (1991) (13)
Constructions of large planar networks with given degree and diameter (1998) (12)
Parameterized Complexity of the Firefighter Problem (2011) (11)
Parameterized complexity: new developments and research frontiers (2001) (11)
On the Complexity of Fixed Parameter Problems (Extended Abstract) (1989) (11)
Simultaneously Satisfying Linear Equations Over $\mathbb{F}_2$: MaxLin2 and Max-$r$-Lin2 Parameterized Above Average (2011) (11)
Fixed-Parameter Algo Algorithms for Kemeny Scores (2008) (11)
Explaining cryptographic systems to the general public (1999) (10)
Train Marshalling Is Fixed Parameter Tractable (2012) (10)
Determining the Winner of a Dodgson Election is Hard (2010) (10)
Searching for K 3,3in linear time (1991) (10)
Haplotype Inference Constrained by Plausible Haplotype Data (2009) (10)
Processor Utilization in a Linearly Connected Parallel Processing System (1988) (9)
W-Hierarchies Defined by Symmetric Gates (2010) (9)
Kernelization Lower Bounds (2013) (9)
Constructive complexity (1991) (9)
Parameterized Low-distortion Embeddings - Graph metrics into lines and trees (2008) (9)
Proving NP-hardness for clique-width I: non-approximability of sequential clique-width (2005) (9)
Combinatorially Based Cryptography for Children (and Adults) (1993) (9)
Computability and Complexity - Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday (2017) (9)
On the Fixed-Parameter Intractability and Tractability of Multiple-Interval Graph Problems (2007) (8)
Multivariate Complexity Theory (2011) (8)
Vertex transversals that dominate (1996) (8)
Milling a Graph with Turn Costs: A Parameterized Complexity Perspective (2010) (7)
Finite-Basis Theorems and a Computation-Integrated Approach to Obstruction Set Isolation (1989) (7)
Computing Kemeny rankings, parameterized by the average K-T distance (2008) (7)
Kernelization for Convex Recoloring (2006) (7)
On the Parameterized Complexity of Dynamic Problems with Connectivity Constraints (2014) (7)
The Parameterized Complexity of Stabbing Rectangles (2012) (7)
Finite-State Computability of Annotations of Strings and Trees (1996) (6)
Radius and diameter in Manhattan lattices (1989) (6)
On the galactic number of a hypercube (1988) (6)
Tractability and hardness of flood-filling games on trees (2015) (6)
Corrigendum to “Advice classes of parameterized tractability” [Ann. Pure Appl. Logic 84 (1) (1997) 119–138] (2018) (6)
Distortion is Fixed Parameter Tractable (2013) (5)
Fixed-Parameter Tractability is Polynomial-Time Extremal Structure Theory I: The Case of Max Leaf (2005) (5)
FPT is characterized by useful obstruction sets: Connecting algorithms, kernels, and quasi-orders (2014) (5)
Counting spanning trees in directed regular multigraphs (1989) (5)
Starting with Nondeterminism: The Systematic Derivation of Linear-Time Graph Layout Algorithms (2003) (5)
Collaborating with Hans: Some Remaining Wonderments (2020) (4)
Parallel self-reducibility (1992) (4)
FPT is P-Time Extremal Structure I (Fixed-parameter tractability is polynomial-time extremal structure theory) (2005) (4)
Kernelization for convex recoloring of trees (2006) (4)
Well-Quasi-Ordering Bounded Treewidth Graphs (2009) (4)
FPT is Characterized by Useful Obstruction Sets (2013) (4)
Sparse Parameterized Problems (1996) (4)
Polynomial-time linear kernelization for cluster editing (2007) (4)
Diversity in Combinatorial Optimization (2019) (4)
Myhill–Nerode Methods for Hypergraphs (2013) (4)
Algorithms, kernels and lower bounds for the Flood-It game parameterized by the vertex cover number (2017) (3)
On the Structure of Parameterized Problems in NP (Extended Abstract) (1994) (3)
Algebraic formulas for counting spanning trees in regular multigraphs (1989) (3)
A brief history of Edward K. Blum and the Journal of Computer and System Sciences (2018) (3)
Editorial: foreword from the guest editors (2003) (3)
Sensing God's Will is Fixed Parameter Tractable (2008) (3)
2 00 2 Parameterized Intractability of Motif Search Problems ∗ (2002) (3)
A Purely Democratic Characterization of W[1] (2008) (3)
A Survey on the Complexity of Flood-Filling Games (2018) (2)
On finding optimal and near-optimal lineal spanning trees (1988) (2)
Special Issue on Parameterized Complexity of Discrete Optimization (2011) (2)
On efficient polynomial-time approximation schemes for problems on planar structures (2009) (2)
Algorithms for learning and teaching sets of vertices in graphs (1994) (2)
Some Open Problems in Parameterized Complexity Related to the Work of Jianer Chen (2014) (2)
The Undirected Feedback Vertex Set Problem has Polynomial Kernel Size (2006) (2)
Parameterized and exact computation : First International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004 : proceedings (2004) (2)
Unplugging Education: Removing barriers to engaging with new disciplines (2012) (1)
Parameterized Control Complexity in Fallback Voting (2010) (1)
Depth-First Search and the Plehn–Voigt Theorem (2013) (1)
Explaining cryptosystems to the general public (2001) (1)
Appendix 2: Menger’s Theorems (2013) (1)
Computers, Complexity, and Intractability from the Parametric Point of View (1999) (1)
Combinatorial Circuits and the W-hierarchy (2007) (1)
Implementing the Standards: Let's Focus on the First Four (1992) (1)
The Flood-It game parameterized by the vertex cover number (2015) (1)
Why Is P Not Equal to NP (2007) (1)
How applying Myhill-Nerode methods to hypergraphs helps mastering the Art of Trellis Decoding (2012) (1)
Provable Intractability: The Class X P (1999) (1)
A Survey of FPT Algorithm Design Techniques with an Emphasis on Recent Advances and Connections to Practical Computing (2004) (1)
Surfing with Rod (2017) (1)
Parameterizing by the Number of Numbers (2011) (1)
Research on Mega-Math: Discrete mathematics and computer science for children. Final report (1995) (1)
Parameterized and Exact Computation (2004) (1)
Abstract Milling with Turn Costs (2009) (0)
Myhill – Nerode Methods for Hypergraphs René (2015) (0)
Other Width Metrics (2013) (0)
Advice classes of parameterized tractability ’ Liming Cai (2003) (0)
The Advice View Revisited and LOGSPACE (1999) (0)
The W -Hierarchy (2013) (0)
Re ned Sear h Tree Te hniquefor Dominating Set on Planar Graphs ? (2007) (0)
Courcelle’s Theorem (2013) (0)
Parameterized String Equations (2021) (0)
Parameterized Complexity News 2 Johan Kwisthout TOP grant (2017) (0)
Bounded Search Trees (2013) (0)
Iterative Compression, and Measure and Conquer, for Minimization Problems (2013) (0)
Well-Quasi-Orderings and the Robertson–Seymour Theorems (2013) (0)
Are you Interested in Theoretical Computer Science? (How Not???) I Have Some Advice for You (2016) (0)
On the Parameterized Complexity of the Structure of Lineal Topologies (Depth-First Spanning Trees) of Finite Graphs: The Number of Leaves (2023) (0)
Applications of the Obstruction Principle and WQOs (2013) (0)
More on Kernelization (2013) (0)
Methods via Automata and Bounded Treewidth (2013) (0)
Master index to volumes 71-80. (2000) (0)
The M-Hierarchy, and XP-Optimality (2013) (0)
The Graph Minor Theorem (2013) (0)
Parameterized Complexity via Combinatorial Circuits ( Extended Abstract ) (0)
Optimization Problems, Approximation Schemes, and Their Relation to FPT (2013) (0)
Myhill-Nerode Methods for Hypergraphs and Applications (2012) (0)
Recent Developments in the Theory of Pre-processing (2011) (0)
Some Other W[1] Hardness Results (2013) (0)
Finding Minor-Order Obstruction Sets : Feedback Vertex Set 2 (2007) (0)
Constructivity Issues in Graph Algorithms (1992) (0)
Beyond W[t]-Hardness (2013) (0)
K-processor Scheduling (1994) (0)
The Structure of Languages Under Parameterized Reducibilities (1999) (0)
Color Coding, Multilinear Detection, and Randomized Divide and Conquer (2013) (0)
Using algebra for massively parallel processor design and utilization (1990) (0)
Appendix 1: Network Flows and Matchings (2013) (0)
Computational Tractability : The View From Mars 1 (2007) (0)
Heuristics for Treewidth (2013) (0)
Fixed Parameter Algorithms (Dagstuhl Seminar 03311) (2021) (0)
New directions in parameterized algorithmics (2016) (0)
Efficient Data Reduction forDominating Set: A Linear Problem Kernel for the Planar Case (Extended Abstract) (2002) (0)
Parameterized Counting and Randomization (2013) (0)
Treewidth and Dynamic Programming (2013) (0)
The Parameterized Complexity of Some Fundamental Problems of Linear Codes and Integer Lattices (1999) (0)
Parameterized Complexity (Dagstuhl Seminar 01311) (2021) (0)
Another Basis for the W-Hierarchy and the Tradeoff Theorem (2013) (0)
Induced minors and related problems (1991) (0)
Algebraic Constructions of E cient Broadcast Networks (2021) (0)
Fixed Parameter Analogues of PSpace and k-Move Games (2013) (0)
Some Ad Hoc Methods: The Methods of Bounded Search Tree and Problem Kernel (1999) (0)
On Solution Discovery via Reconfiguration (2023) (0)
The Parameterized Complexity of Stabbing Rectangles (2010) (0)
Relationships with Classical Complexity and Limited Nondeterminism (1999) (0)
Index sets and parametric reductions (2001) (0)
More on Width-Metrics: Applications and Local Treewidth (2013) (0)
The Monotone and Antimonotone Collapse Theorems: Monotone W [2 t +1]= W [2 t ] and Antimonotone W [2 t +2]= W [2 t +1] (2013) (0)
Another Basis for the W -Hierarchy, the Tradeoff-Theorem, and Randomized Reductions (1999) (0)
The Basic Class W[1] and an Analog of Cook’s Theorem (2013) (0)
Improved Kernelization and Linear Time FPT for Convex Recoloring of Trees ? (0)
Fixed-Parameter Compl ex i t y and Cryptography (0)
Further Elementary Techniques (2013) (0)

This paper list is powered by the following services:

Other Resources About Michael Fellows

en.wikipedia.org

What Schools Are Affiliated With Michael Fellows?

Michael Fellows is affiliated with the following schools: