The University of Newcastle, Researcher report.

Funded Projects

Please note, only grants administered through the University of Newcastle Research Office are recorded here. For a more complete picture of the researcher's grant history a Personal URL may be supplied, above.

Research Publications

Please note, the publications listed here:
(1) relate to the researcher's position at the University of Newcastle only
(2) are for selected categories of publications, and
(3) relate to publication year 1998, onwards.
For a more complete picture of the researcher's publication history a Personal URL may be supplied at the top of this page.

Journal Article

Fellows Michael Ralph, Knauer C, Nishimura N, Ragde P, Rosamond Frances Ann, Stege U, Thilikos D M, Whitesides S, ’Faster fixed-parameter tractable algorithms for matching and packing problems’, Algorithmica, 52 167-176 (2008) [C1]

Dujmovic V, Fellows Michael Ralph, Kitching M, Liotta G, McCartin C, Nishimura N, Ragde P, Rosamond Frances Ann, Whitesides S, Wood D R, ’On the parameterized complexity of layered graph drawing’, Algorithmica, 52 267-292 (2008) [C1]

Downey Rodney G, Fellows Michael Ralph, Langston Michael A, ’The computer journal special issue on parameterized complexity: Foreword by the guest editors’, Computer Journal, 51 1-6 (2008) [C3]

Dehne F, Fellows Michael Ralph, Langston M, Rosamond Frances Ann, Stevens K, ’An O(2(O(k))n(3)) FPT algorithm for the undirected feedback vertex set problem’, Theory of Computing Systems, 41 479-492 (2007) [C1]

Abu-Khzam F N, Fellows Michael Ralph, Langston M A, Suters W H, ’Crown structures for vertex cover kernelization’, Theory of Computing Systems, 41 411-430 (2007) [C1]

Christian R, Fellows Michael Ralph, Rosamond Frances Ann, Slinko A, ’On complexity of lobbying in multiple referenda’, Review of Economic Design, 11 217-224 (2007) [C1]

Cai L, Fellows Michael Ralph, Juedes D, Rosamond Frances Ann, ’The complexity of polynomial-time approximation’, Theory of Computing Systems, 41 459-477 (2007) [C1]

Dujmovic V, Fellows Michael Ralph, Hallett M, Kitching M, Liotta G, McCartin C, Nishimura N, Ragde P, Rosamond Frances Ann, Suderman M, Whitesides S, Wood D R, ’A fixed-parameter approach to 2-layer planarization’, Algorithmica, 45 159-182 (2006) [C1]

Fellows Michael Ralph, Szeider S, Wrightson Graham, ’On finding short resolution refutations and small unsatisfiable subsets’, Theoretical Computer Science, 351 351-359 (2006) [C1]

Fellows Michael Ralph, Gramm J, Niedermeier R, ’On the parameterized intractability of motif search problems’, Combinatorica, 26 141-167 (2006) [C1]

Alber Jochen, Fan Hongbing, Fellows Michael Ralph, Fernau Henning, Niedermeier Rolf, Rosamond Frances Ann, Stege Ulrike, ’A refined search tree technique for Dominating Set on planar graphs’, Journal of Computer and System Sciences, 71 385-405 (2005) [C1]

Chen Jianer, Chor Benny, Fellows Michael Ralph, Huang Xiuzhen, Juedes David, Kanj Iyad A, Xia Ge, ’Tight lower bounds for certain parameterized NP-hard problems’, Information and Computation, 201 216-231 (2005) [C1]

Alber J, Fellows Michael Ralph, Niedermeier, ’Polynomial-Time Data Reduction for Dominating Set’, Journal of the ACM, 51 363-384 (2004) [C1]

Ellis J, Fan H, Fellows Michael Ralph, ’The Dominating set problem is fixed parameter tractable for graphs of bounded genus’, Journal of Algorithms, 52 152-168 (2004) [C1]

Fellows Michael Ralph, Michael Hallett, Ulrike Stege, ’Analogs & duals of the MAST problem for sequences & trees’, Journal of Algorithms, 49 192-216 (2003) [C1]

Downey R, Estivill-Castro Vladimir, Fellows Michael Ralph, Prieto-Rodriguez Elena, Rosamond Frances Ann, ’Cutting up is hard to do: the parameterized Complexity of k-Cut and Related Probelms’, Electronic Notes in Theoretical Computer Science, 78 205-218 (2003) [C1]

Bell T, Thimbleby H, Fellows Michael Ralph, Witten I, Koblitz N, Powell M, ’Explaining cryptographic systems’, Computers & Education, 40 199-215 (2003) [C1]

Chen J, Fellows Michael Ralph, ’Foreword from the guest editors’, Journal of Computer and System Sciences, 67 653 (2003) [C3]

Review

Estivill-Castro V, Fellows Michael Ralph, Langston M A, Rosamond Frances Ann, ’Max Leaf Spanning Tree’, Encyclopedia of Algorithms (2008) [D2]

Conference Publication

Fellows Michael Ralph, Hermelin D, Muller M, Rosamond Frances Ann, ’A purely democratic characterization of W[1]’, Parameterized and Exact Computation, Victoria, BC (2008) [E1]

Bodlaender H L, Fellows Michael Ralph, Heggernes P, Mancini Federico, Papadopoulos C, Rosamond Frances Ann, ’Clustering with Partial Information’, Mathematical Foundations of Computer Science 2008, Torun, Poland (2008) [E1]

Fellows Michael Ralph, Fernau Henning, ’Facility location problems: A parameterized view’, Lecture Notes in Computer Science, Shanghai, China (2008) [E1]

Betzler Nadja, Fellows Michael Ralph, Guo Jiong, Niedermeier Rolf, Rosamond Frances Ann, ’Fixed-parameter algorithms for Kemeny Scores’, Algorithmic Aspects in Information and Management. 4th International Conference, AAIM 2008, Shanghai, China (2008) [E1]

Bodlaender Hans L, Downey Rodney G, Fellows Michael Ralph, Hermelin Danny, ’On problems without polynomial kernels’, Automata, Languages and Programming, Reykjavik (2008) [E1]

Betzler Nadja, Fellows Michael Ralph, Komusiewicz Christian, Niedermeier Rolf, ’Parameterized algorithms and hardness results for some graph Motif problems’, Combinatorial Pattern Matching, Pisa, Italy (2008) [E1]

Chor B, Fellows Michael Ralph, Ragan M A, Razgon I, Rosamond Frances Ann, Snir S, ’Connected coloring completion for general graphs: Algorithms and complexity’, Computing and Combinatorics. 13th Annual International Conference, COCOON 2007. Proceedings, Banff, Canada (2007) [E1]

Fellows Michael Ralph, Langston M, Rosamond Frances Ann, Shaw Peter Edward, ’Efficient parameterized preprocessing for cluster editing’, Fundamentals of Computation Theory. 16th International Symposium, FCT 2007 Budapest, Hungary, August 27-30, 2007 Proceedings, Budapest, Hungary (2007) [E1]

Fellows Michael Ralph, Fornin F V, Lokshtanov D, Rosamond Frances Ann, Saurabh S, Szeider S, Thomassen C, ’On the complexity of some colorful problems parameterized by treewidth’, Combinatorial Optimization and Applications. First International Conference Proceedings, Xi'an, China (2007) [E1]

Fellows Michael Ralph, Flum J, Hermelin D, Muller M, Rosamond Frances Ann, ’Parameterized complexity via combinatorial circuits’, Algorithms and Complexity: Proceedings of the Third ACiD Workshop, Durham, UK (2007) [E1]

Bodlaender H, Fellows Michael Ralph, Langston M, Ragan M A, Rosamond Frances Ann, Weyer M, ’Quadratic kernelization for convex recoloring of trees’, Computing and Combinatorics. 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007. Proceedings, Banff, Canada (2007) [E1]

Fellows Michael Ralph, Fertin G, Hermelin D, Vialette S, ’Sharp tractability borderlines for finding connected motifs in vertex-colored graphs’, Automata, Languages and Programming. 34th International Colloquium, ICALP 2007, Wrocaw, Poland (2007) [E1]

Fellows Michael Ralph, Rosamond Frances Ann, ’The complexity ecology of parameters: An illustration using bounded max leaf number’, Computation and Logic in the RealWorld. Third Conference on Computability in Europe, CiE 2007, Siena, Italy (2007) [E1]

Fellows Michael Ralph, Rosamond Frances Ann, ’Why is P not equal to NP?’, Computation and Logic in the Real World: Third Conference on Computability in Europe, CiE 2007: Local Proceedings, Siena, Italy (2007) [E1]

Fellows Michael Ralph, Rosamond Frances Ann, Rotics U, Szeider S, ’Clique width Minimization is NP-hard’, STOC '06 Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA (2006) [E1]

Bodlaender Hans L, Fellows Michael Ralph, Langston Michael A, Ragan Mark A, Rosamond Frances Ann, Weyer Mark, ’Kernelization for Convex Recoloring of Trees’, Algorithms and Complexity in Durham 2006, Proceedings of the Second ACiD Workshop (Texts in Algorithmics 7), London (2006) [E1]

Dehne F, Fellows Michael Ralph, Fernau Henning, Prieto-Rodriguez Elena, Rosamond Frances Ann, ’NONBLOCKER: Parameterized algorithmics for MINIMUM DOMINATING SET’, Lecture Notes in Computer Science (SOFSEM 2006: 32nd Conference on Current Trends in Theory and Practice of Computer Science), Merin, Czech Republic (2006) [E1]

Christian Robin, Fellows Michael Ralph, Rosamond Frances Ann, Slinko Arkadii, ’On Complexity of Lobbying in Multiple Referenda’, 1st International Workshop on Computational Social Choice, Amsterdam (2006) [E1]

Downey R G, Fellows Michael Ralph, McCartin C, ’Parameterized approximation problems’, Lecture Notes in Computer Science (Parameterized and Exact Computation. Second International Workshop, IWPEC 2006 Proceedings), Z?rich, Switzerland (2006) [E1]

Fellows Michael Ralph, ’The lost continent of polynomial time: Preprocessing and kernelization’, Lecture Notes in Computer Science (Parameterized and Exact Computation. Second International Workshop, IWPEC 2006 Proceedings), Z?rich, Switzerland (2006) [E1]

Burrage K, Estivill-Castro V, Fellows Michael Ralph, Langston M, Mac S, Rosamond Frances Ann, ’The undirected feedback vertex set problem has a poly(k) kernel’, Lecture Notes in Computer Science (Parameterized and Exact Computation. Second International Workshop, IWPEC 2006 Proceedings), Z?rich, Switzerland (2006) [E1]

Dehne F, Fellows Michael Ralph, Rosamond Frances Ann, Langston M A, Stevens K, ’An O(2O(k)n3) FPT algorithm for the undirected feedback vertex set problem’, Proceedings of Computing and Combinatorics: 11th Annual International Conference, COCOON 2005, Kunming, China (2005) [E1]

Fellows Michael Ralph, Estivill-Castro Vladimir, Langston M, Rosamond Frances Ann, ’Fixed-Parameter Tractability is Polynomial-Time Extremal Structure Theory I: The Case of Max Leaf’, Algorithms and complexity in Durham 2005 : proceedings of the first ACiD workshop, University of Durham (2005) [E1]

Fellows Michael Ralph, ’A Survey of FPT algorithm design techniques with an emphasis on recent advances and connections to practical computing’, Lecture Notes in Computer Science, Bergen, Norway (2004) [E1]

Fellows Michael Ralph, Knauer N, Nishimura N, Radge P, Rosamond Frances Ann, Stege U, Thilikos Dm, Whitesides S, ’Faster fixed-parameter tractable algorithms for matching and packing problems’, Algorithms - ESA 2004 : 12th annual European symposium, proceedings : Lecture Notes in computer Science, Bergen, Norway (2004) [E1]

Fellows Michael Ralph, Heggernes P, Rosamond Frances Ann, Sloper C, Arne Telle J, ’Finding k disjoint triangles in an arbitrary graph’, Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004 : Lecture Notes in Computer Science, Bad Honnef, Germany (2004) [E1]

Dehne F, Fellows Michael Ralph, Rosamond Frances Ann, Shaw Peter Edward, ’Greedy localisation, iterative compression, and modeled crown reductions: New FPT techniques, an improved algorithm for set splitting, and a novel 2k kernelization for vertex cover’, Conference Paper, Bergen, Norway (2004) [E1]

Abu-Khzam F N, Collins R, Fellows Michael Ralph, Lanston M A, Suters W A, Symons C T, ’Kernelization algorithms for the vertex cover problem: Theory and experiments’, Proceedings ALENEX/ANALC 2004: Lecture Notes in Computer Science, New Orleans, La (2004) [E3]

Fellows Michael Ralph, Juedes D, Chor B, ’Linear Kernels in Linear Time, or How to Save k Colours in O(n2) Steps’, Proceedings WG 2004, Springer-Verlag, Lecture Notes in Computer Science 3353, Bad Honnef, Germany (2004) [E1]

Fellows Michael Ralph, Stefan Szeider, Wrightson Graham, ’On finding short resolution refutations and small unsatisfiable subsets’, parameterized and Exact Computation, Bergen, Norway (2004) [E1]

Downey Rod, Fellows Michael Ralph, Dehne Frank, ’Parameterized and Exact Computation’, Conference Proceedings No LNCS3162, Bergen, Norway (2004) [E4]

Dehne F, Fellows Michael Ralph, Rosamond Frances Ann, ’An FPT Algorithm for set splitting’, Lecture Notes in Computer Science, Elspeet, The Netherlands (2003) [E1]

Fellows Michael Ralph, ’Blow-ups, win/wins, and crown rules: some new directions in FPT’, Lecture Notes in Computer Science, Elspeet, Netherlands (2003) [E1]

Fellows Michael Ralph, ’New directions and new challenges in algorithm design and complexity, parameterized’, Lecture Notes in Computer Science, Ottowa, Ontario Canada (2003) [E1]

Bodlaender H L, Fellows Michael Ralph, Thilikos D M, ’Starting with Nondeterminism: The Systematic derivation of linear-time graph layout algorithms’, Lecture Notes in Computer Science, Bratislava, Slovakia (2003) [E1]

Alber J, Fellows Michael Ralph, Niedermeier R, ’Efficient data reduction for dominating set: a linear problem kernel for the planar case’, Lecture Notes in Computer Science, Turku, Finland (2002) [E1]

Fellows Michael Ralph, Gramm J, Neidermeier R, ’On the parameterized intractability of CLOSEST SUBSTRING and related problems’, Lecture Notes in Computer Science, Antibes-Juan les Pins, France (2002) [E1]

Fellows Michael Ralph, ’Parameterized complexity: the main ideas and connections to practical computing’, Experimental algorithmics : from algorithm design to robust and efficient software /, Dagstuhl Castle, Germany (2002) [E1]

Fellows Michael Ralph, ’Parameterized Complexity: The Main Ideas and Some Research Frontiers’, Algorithms and Computation, Christchurch, New Zealand (2001) [E1]

Fellows Michael Ralph, ’Some New Complexity in Parameterized Complexity’, Proceedings of the Twelfth Australasian Workshop on Combinatorial Algorithms, Bandung, Indonesia (2001) [E3]

Fellows Michael Ralph, ’Some new developments in parameterized complexity’, Proceedings 12th Australasian Workshop on Combinatorial Algorithms, Lembang, Indonesia (2001) [E3]

Return to Search page