(Meta) Kernelization

(Meta) Kernelization

40th international colloquium on automata, languages and programming

A $c^k n$ 5-Approximation Algorithm for Treewidth

A 3-approximation for the pathwidth of Halin graphs

A 3-approximation for the pathwidth of Halin graphs

A Linear Vertex Kernel for Maximum Internal Spanning Tree

A Note on Exact Algorithms for Vertex Ordering Problems on Graphs

scholarly article by Hans L. Bodlaender et al published 21 January 2011 in Theory of Computing Systems

A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs

A Polynomial Kernel for Proper Interval Vertex Deletion

A Polynomial Kernel for Proper Interval Vertex Deletion

A Subexponential Parameterized Algorithm for Proper Interval Completion

A Subexponential Parameterized Algorithm for Proper Interval Completion

A linear vertex kernel for maximum internal spanning tree

A measure & conquer approach for the analysis of exact algorithms

scholarly article by Fedor Fomin et al published 1 August 2009 in Journal of the ACM

AT-free graphs: linear bounds for the oriented diameter

Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem

Algorithm for finding k-vertex out-trees and its application to k-internal out-branching problem

Algorithms Parameterized by Vertex Cover and Modular Width, Through Potential Maximal Cliques

Algorithms Parameterized by Vertex Cover and Modular Width, through Potential Maximal Cliques

Algorithms for graphs with small octopus

scholarly article by Fedor Fomin et al published January 2004 in Discrete Applied Mathematics

Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width

article by Fedor Fomin et al published January 2014 in SIAM Journal on Computing

An Exact Algorithm for Minimum Distortion Embedding

An O(c^k n) 5-Approximation Algorithm for Treewidth

An annotated bibliography on guaranteed graph searching

An exact algorithm for minimum distortion embedding

Approximating Width Parameters of Hypergraphs with Excluded Minors

Approximating minimum cocolorings

Approximation Algorithms for Domination Search

Approximation algorithms for time-dependent orienteering

scholarly article by Fedor Fomin & Andrzej Lingas published July 2002 in Information Processing Letters

Approximation of minimum weight spanners for sparse graphs

Approximation of pathwidth of outerplanar graphs

Backbone colorings for graphs: Tree and path backbones

Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs

Bidimensional Parameters and Local Treewidth

Bounding the Number of Minimal Dominating Sets: A Measure and Conquer Approach

Branch and Recharge: Exact Algorithms for Generalized Domination

Branching and Treewidth Based Exact Algorithms

scholarly article by Fedor Fomin et al published 2006 in Lecture Notes in Computer Science

Catalan structures and dynamic programming in H-minor-free graphs

Combinatorial bounds via measure and conquer

article published in 2008

Compound Logics for Modification Problems

scientific article published on 20 September 2024

Computing Branchwidth Via Efficient Triangulations and Blocks

Computing Optimal Steiner Trees in Polynomial Space

Computing Tree-Depth Faster Than $$2^{n}$$ 2 n

Computing Tree-Depth Faster Than 2 n

Computing branchwidth via efficient triangulations and blocks

Connected Graph Searching in Outerplanar Graphs

Connected graph searching

Contraction Bidimensionality: The Accurate Picture

Contraction obstructions for treewidth

Cops and Robber Game Without Recharging

Cops and Robber Game without Recharging

Cops and Robber with Constraints

Counting Subgraphs via Homomorphisms

Counting Subgraphs via Homomorphisms

Distortion Is Fixed Parameter Tractable

Distortion is Fixed Parameter Tractable

Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up

Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms

Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions

scholarly article by Frederic Dorn et al published 2005 in Lecture Notes in Computer Science

Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Decompositions

Eliminating graphs by means of parallel knock-out schemes

Enumerating Minimal Subset Feedback Vertex Sets

Enumerating Minimal Subset Feedback Vertex Sets

Equitable colorings of bounded treewidth graphs

Exact Algorithm for the Maximum Induced Planar Subgraph Problem

Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs

Exact Algorithms for Graph Homomorphisms

Exact Algorithms for Treewidth and Minimum Fill-In

scholarly article by Fedor Fomin et al published January 2008 in SIAM Journal on Computing

Exact algorithms via monotone local search

Exact exponential algorithms

scholarly article by Fedor Fomin & Petteri Kaski published 1 March 2013 in Communications of the ACM

Exploring the Subexponential Complexity of Completion Problems

FPT Suspects and Tough Customers: Open Problems of Downey and Fellows

article published in 2012

Fast Exact Algorithms for Hamiltonicity in Claw-Free Graphs

Fast Minor Testing in Planar Graphs

Fast Minor Testing in Planar Graphs

Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus

Faster Exact Algorithms for Some Terminal Set Problems

Faster Parameterized Algorithms for Minor Containment

Faster algorithms for finding and counting subgraphs

Faster parameterized algorithms for minor containment

Foreword: Special Issue on Theory and Applications of Graph Searching Problems

Forewords: Special issue on Theory and Applications of Graph Searching Problems

Forewords: Special issue on graph searching

Going Far From Degeneracy

scholarly article published in 2020

Graph Modification Problems: A Modern Perspective

Graph Searching, Elimination Trees, and a Generalization of Bandwidth

Guard Games on Graphs: Keep the Intruder Out!

Guard games on graphs: Keep the intruder out!

article published in 2011

Hitting Forbidden Minors: Approximation and Kernelization

How to Guard a Graph?

article published in 2010

How to Guard a Graph?

How to hunt an invisible rabbit on a graph

Implicit branching and parameterized partial cover problems

Improved Exact Algorithms for Counting 3- and 4-Colorings

scholarly article published in Lecture Notes in Computer Science

Improved algorithms for feedback vertex set problems

scholarly article by Jianer Chen et al published November 2008 in Journal of Computer and System Sciences

Iterative Compression and Exact Algorithms

scholarly article published in Lecture Notes in Computer Science

Iterative compression and exact algorithms

Kernel(s) for problems with no kernel

Kernelization

Kernelization Algorithms

algorithms creating a kernel from a given graph

Kernelization Methods for Fixed-Parameter Tractability

Kernels for feedback arc set in tournaments

Large Induced Subgraphs via Triangulations and CMSO

Largest Chordal and Interval Subgraphs Faster Than 2 n

Largest Chordal and Interval Subgraphs Faster than $$2^n$$ 2 n

Local search: Is brute-force avoidable?

Long Circuits and Large Euler Subgraphs

Long Circuits and Large Euler Subgraphs

Lower Bounds for the Graph Homomorphism Problem

Making Life Easier for Firefighters

article by Fedor Fomin et al published 2012 in Lecture Notes in Computer Science

Measure and conquer

Metric Dimension of Bounded Width Graphs

Minimizing Rosenthal Potential in Multicast Games

Minimum Fill-in of Sparse Graphs: Kernelization and Approximation

Mixed search number and linear-width of interval and split graphs

More About Subcolorings

New upper bounds on the decomposability of planar graphs

Nondeterministic Graph Searching: From Pathwidth to Treewidth

On Two Techniques of Combining Branching and Treewidth

On distance constrained labeling of disk graphs

article by Jiří Fiala et al published October 2004 in Theoretical Computer Science

On exact algorithms for treewidth

On maximum number of minimal dominating sets in graphs

On self duality of pathwidth in polyhedral graph embeddings

On the Complexity of Reconstructing H-free Graphs from Their Star Systems

On the Complexity of Some Colorful Problems Parameterized by Treewidth

On the Domination Search Number

On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms

scholarly article by Fedor Fomin et al published 8 December 2007 in Algorithmica

On the Parameterized Complexity of Cutting a Few Vertices from a Graph

On the complexity of reconstructing H-free graphs from their Star Systems

On the complexity of some colorful problems parameterized by treewidth

On the domination search number

On the monotonicity of games generated by symmetric submodular functions

On the parameterized complexity of vertex cover and edge cover with connectivity constraints

On tractability of Cops and Robbers game

Parameterized Algorithms

scholarly article published 2015

Parameterized Algorithms to Preserve Connectivity

Parameterized Complexity of Firefighting Revisited

Parameterized Complexity of Secluded Connectivity Problems

Parameterized Complexity of Superstring Problems

Parameterized Complexity of Superstring Problems

Parameterized Complexity of the Spanning Tree Congestion Problem

Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree

Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree

scientific article published in 2019

Parameterized algorithm for eternal vertex cover

scholarly article by Fedor Fomin et al published July 2010 in Information Processing Letters

Parameterized complexity of connected even/odd subgraph problems

Parameterized complexity of firefighting

scholarly article by Cristina Bazgan et al published November 2014 in Journal of Computer and System Sciences

Parameterized complexity of the anchored k -core problem for directed graphs

Pathwidth of Planar and Line Graphs

Pathwidth of cubic graphs and exact algorithms

scholarly article by Fedor Fomin & Kjartan Høie published March 2006 in Information Processing Letters

Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms

article published in 2012

Planar Graph Coloring Avoiding Monochromatic Subgraphs: Trees and Paths Make It Difficult

Preface to Special Issue Dedicated to the 60th Birthday of Gregory Gutin

scientific article published in 2018

Preprocessing Subgraph and Minor Problems: When Does a Small Vertex Cover Help?

article by Fedor Fomin et al published 2012 in Lecture Notes in Computer Science

Preprocessing subgraph and minor problems: When does a small vertex cover help?

article by Fedor Fomin et al published March 2014 in Journal of Computer and System Sciences

Pursuing a fast robber on a graph

Quadratic Upper Bounds on the Erdős-Pósa Property for a Generalization of Packing and Covering Cycles

Radio Labeling with Preassigned Frequencies

Rank-width and tree-width of H -minor-free graphs

Ranking and Drawing in Subexponential Time

Representative Families of Product Families

Representative Sets of Product Families

Searching expenditure and interval graphs

Searching for better fill-in

Sharp Separation and Applications to Exact and Parameterized Algorithms

Sharp Separation and Applications to Exact and Parameterized Algorithms

article published in 2010

Social choice meets graph drawing: How to get subexponential time algorithms for ranking and drawing problems

Solving Connected Dominating Set Faster than 2 n

Sort and Search: Exact algorithms for generalized domination

scholarly article by Fedor Fomin et al published June 2009 in Information Processing Letters

Spanners in Sparse Graphs

Spanners in sparse graphs

Spanners of bounded degree graphs

scholarly article by Fedor Fomin et al published January 2011 in Information Processing Letters

Spanning Directed Trees with Many Leaves

Special Issue on Parameterized Complexity of Discrete Optimization

Strengthening Erdös-Pósa property for minor-closed graph classes

Subexponential Parameterized Algorithm for Computing the Cutwidth of a Semi-complete Digraph

Subexponential Parameterized Algorithm for Minimum Fill-In

Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering

Subexponential algorithms for partial cover problems

scholarly article by Fedor Fomin et al published August 2011 in Information Processing Letters

Subexponential parameterized algorithms

Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs

scholarly article by Erik D. Demaine et al published 1 November 2005 in Journal of the ACM

The Curse of Connectivity: t-Total Vertex (Edge) Cover

The Firefighter problem on graph classes

Three Complexity Results on Coloring P k -Free Graphs

Three complexity results on coloringPk-free graphs

Tight bounds for parameterized complexity of Cluster Editing with a small number of clusters

To Satisfy Impatient Web Surfers Is Hard

To satisfy impatient Web surfers is hard

Tree decompositions with small cost

article published in 2005

Treewidth Computation and Extremal Combinatorics

Treewidth computation and extremal combinatorics

Vertex Cover Structural Parameterization Revisited

k-Gap Interval Graphs