New Algorithms for k-Face Cover, k-Feedback Vertex Set, and k -Disjoint Cycles on Plane and Planar Graphs

No abstract is available for this paper.

• Publication year

  2002

• Venue

  International Workshop on Graph-Theoretic Concepts in Computer Science

• Publication date

  2002-06-13

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/3-540-36379-3_25
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Parameterized complexity: exponential speed-up for planar graph problems

  2001cited by this paper
• Face Covers and the Genus Problem for Apex Graphs

  2001cited by this paper
• Refined Search Tree Technique for Dominating Set on Planar Graphs 1

  2001cited by this paper
• Graph Separators: A Parameterized View

  2001cited by this paper
• Maximum Clique Transversals

  2001cited by this paper
• Subexponential Parameterized Algorithms Collapse the W-Hierarchy

  2001cited by this paper
• Fixed Parameter Algorithms for PLANAR DOMINATING SET and Related Problems

  2000cited by this paper
• Faster algorithms for domination of planar graphs

  2000cited by this paper
• Parameterized Complexity

  1998influential reference
• Graph Theory

  1997cited by this paper
• Parameterized Computational Feasibility

  1995cited by this paper
• A linear time algorithm for finding tree-decompositions of small treewidth

  1993cited by this paper
• Efficient Sets in Partial k-Trees

  1993cited by this paper
• On Disjoint Cycles

  1991cited by this paper
• Nonconstructive tools for proving polynomial-time decidability

  1988cited by this paper
• On Independent Circuits Contained in a Graph

  1965cited by this paper

• A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs

  2026cites this paper
• Jones’ Conjecture for Halin Graphs and a Bit More

  2024cites this paper
• Planarizing Graphs and their Drawings by Vertex Splitting

  2022cites this paper
• Approximability of the Independent Feedback Vertex Set Problem for Bipartite Graphs

  2020cites this paper
• WALCOM: Algorithms and Computation: 14th International Conference, WALCOM 2020, Singapore, Singapore, March 31 – April 2, 2020, Proceedings

  2020cites this paper
• Jones' Conjecture in subcubic graphs

  2019cites this paper
• Flow-Cut Gaps and Face Covers in Planar Graphs

  2018cites this paper
• Planar Vertex-Disjoint Cycle Packing: New Structures and Improved Kernel

  2017cites this paper
• On line graphs of subcubic triangle-free graphs

  2017cites this paper
• Treewidth: algorithmic, combinatorial, and practical aspects. (Treewidth: aspects algorithmiques, combinatoires et pratiques)

  2017cites this paper
• An O(logOPT)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log \mathrm {OPT})$$\end{document}-Approximation for Co

  2017cites this paper
• Coverability and Fast Sub-exponential Parameterized Algorithms in Planar Graphs ∗

  2017cites this paper
• An O(log OPT)-approximation for covering and packing minor models of the pumpkin

  2016cites this paper
• On some classical and new hypergraph invariants

  2016influential citation
• Sur quelques invariants classiques et nouveaux des hypergraphes

  2016influential citation
• Recent techniques and results on the Erdős-Pósa property

  2016cites this paper
• Recent techniques and results on the Erd\H{o}s-P\'osa property

  2016influential citation
• Structural and algorithmic aspects of partial orderings of graphs. (Aspects structurels et algorithmiques des ordres partiels sur les graphes)

  2016cites this paper
• 12th Cologne-Twente workshop on graphs and combinatorial optimization (CTW 2013)

  2015cites this paper
• An O(log OPT)-approximation for covering and packing minor models of $θr

  2015cites this paper
• Bidimensionality and Parameterized Algorithms (Invited Talk)

  2015cites this paper
• Review of: Fundamentals of Parameterized Complexity by Rodney G. Downey and Michael R. Fellows

  2015cites this paper
• Approximation and Online Algorithms

  2015cites this paper
• Algorithms for the Independent Feedback Vertex Set Problem

  2015cites this paper
• A linear kernel for planar red-blue dominating set

  2014cites this paper
• On cycle packings and feedback vertex sets

  2014cites this paper
• Deterministic Algorithms for the Independent Feedback Vertex Set Problem

  2014cites this paper
• Parameter ecology for Feedback Vertex Set

  2014cites this paper
• Near-Linear Time Constant-Factor Approximation Algorithm for Branch-Decomposition of Planar Graphs

  2014cites this paper
• Approximate min-max relations on plane graphs

  2013cites this paper
• The M-Hierarchy, and XP-Optimality

  2013cites this paper
• The role of planarity in connectivity problems parameterized by treewidth

  2013cites this paper
• On the Parameterized Complexity of Computing Graph Bisections

  2013cites this paper
• A linear-time kernelization for the Rooted k-Leaf Outbranching Problem

  2013cites this paper
• On the Parameterized Complexity of Computing Balanced Partitions in Graphs

  2013cites this paper
• The decycling number of outerplanar graphs

  2012cites this paper
• FEEDBACK VERTEX SET ON PLANAR GRAPHS

  2012influential citation
• New Width Parameters of Graphs

  2012cites this paper
• A note on disjoint cycles

  2012cites this paper
• Simpler Linear-Time Kernelization for Planar Dominating Set

  2011cites this paper
• Fast Sub-exponential Algorithms and Compactness in Planar Graphs

  2011cites this paper
• Approximate tree decompositions of planar graphs in linear time

  2011cites this paper
• Discrete Descriptions of Geometric Objects

  2011cites this paper
• Confronting intractability via parameters

  2011cites this paper
• Approximate min-max relations on plane graphs

  2011cites this paper
• Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Decompositions

  2010cites this paper
• (Meta) Kernelization

  2009cites this paper
• Kernel bounds for disjoint cycles and disjoint paths

  2009cites this paper
• Feedback vertex set on graphs of low clique-width

  2009cites this paper
• A Linear Kernel for Planar Feedback Vertex Set

  2008cites this paper
• Linearity of grid minors in treewidth with applications through bidimensionality

  2008cites this paper
• The Bidimensionality Theory and Its Algorithmic Applications

  2008cites this paper
• Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms

  2008cites this paper
• A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs

  2008influential citation
• Bidimensionality and Graph Decompositions

  2008cites this paper
• Analysis of Data Reduction: Transformations give evidence for non-existence of polynomial kernels

  2008cites this paper
• Designing Subexponential Algorithms: Problems, Techniques & Structures

  2007cites this paper
• Faces in the Crowd : On the Algorithmic Utility of Disks and Covers ?

  2007cites this paper
• Improved bottleneck domination algorithms

  2006cites this paper
• Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner’s Contraction

  2006cites this paper
• Bidimensionality, Map Graphs, and Grid Minors

  2005cites this paper
• Bidimensionality: new connections between FPT algorithms and PTASs

  2005cites this paper
• Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs

  2005cites this paper
• Parameterized Algorithmics: A Graph-Theoretic Approach

  2005cites this paper
• Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality

  2005cites this paper
• Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors

  2005cites this paper
• Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions

  2005cites this paper
• Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs

  2005influential citation
• The Bidimensional Theory of Bounded-Genus Graphs

  2004cites this paper
• Fast Parameterized Algorithms for Graphs on Surfaces: Linear Kernel and Exponential Speed-Up

  2004cites this paper
• Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth

  2004cites this paper
• Subexponential parameterized algorithms on graphs of bounded-genus and H-minor-free graphs

  2004cites this paper
• A Geometric Approach to Parameterized Algorithms for Domination Problems on Planar Graphs

  2004cites this paper
• Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs

  2003cites this paper
• Exact algorithms for NP hard problems on networks: design, analysis and implementation

  2002cites this paper
• Parameterized complexity: exponential speed-up for planar graph problems

  2001cites this paper