Fixed‐parameter tractability results for full‐degree spanning tree and its dual

No abstract is available for this paper.

• Publication year

  2006

• Venue

  Networks

• Publication date

  2006-09-13

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1002/net.20353
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A Moderately Exponential Time Algorithm for Full Degree Spanning Tree

  2008cited by this paper
• Combinatorial Optimization on Graphs of Bounded Treewidth

  2008cited by this paper
• The Bidimensionality Theory and Its Algorithmic Applications

  2008cited by this paper
• Invitation to data reduction and problem kernelization

  2007cited by this paper
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs

  2007cited by this paper
• Techniques for Practical Fixed-Parameter Algorithms

  2007cited by this paper
• Invitation to fixed-parameter algorithms

  2007influential reference
• NONBLOCKER: Parameterized Algorithmics for minimum dominating set

  2006cited by this paper
• The Lost Continent of Polynomial Time: Preprocessing and Kernelization

  2006cited by this paper
• Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series)

  2006cited by this paper
• Combinatorial algorithms to cope with the complexity of biological networks

  2006cited by this paper
• Parameterized Complexity Theory

  2006influential reference
• Treewidth: Characterizations, Applications, and Computations

  2006cited by this paper
• Experiments on data reduction for optimal domination in networks

  2006cited by this paper
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size

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

  2005cited by this paper
• FPT is P-Time Extremal Structure I

  2005cited by this paper
• Fast Parameterized Algorithms for Graphs on Surfaces: Linear Kernel and Exponential Speed-Up

  2004cited by this paper
• Polynomial-time data reduction for dominating set

  2002cited by this paper
• Degree-preserving trees

  2000influential reference
• The full‐degree spanning tree problem

  2000influential reference
• Coordinatized Kernels and Catalytic Reductions: An Improved FPT Algorithm for Max Leaf Spanning Tree and Other Problems

  2000cited by this paper
• On local search and placement of meters in networks

  2000cited by this paper
• The full degree spanning tree problem

  1999cited by this paper
• Vertex Cover: Further Observations and Further Improvements

  1999cited by this paper
• Parameterized Complexity

  1998influential reference
• Call routing and the ratcatcher

  1994cited by this paper
• Treewidth

  1994cited by this paper
• Treewidth, Computations and Approximations

  1994cited by this paper
• Easy Problems for Tree-Decomposable Graphs

  1991cited by this paper
• Implicit Network Calibration

  1989cited by this paper
• Interpolation theorem for the number of degree-preserving vertices of spanning trees

  1987cited by this paper
• Explicit Pipe Network Calibration

  1986cited by this paper

• Full degree spanning trees in random regular graphs

  2022cites this paper
• A Retrospective on (Meta) Kernelization

  2020cites this paper
• Some Contributions to Parameterized Complexity

  2018cites this paper
• Excluded Grid Minors and EPTAS

  2018influential citation
• A 43k Kernel for Planar Dominating Set using Computer-Aided Reduction Rule Discovery

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

  2015cites this paper
• Planar graph vertex partition for linear problem kernels

  2013cites this paper
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions

  2012cites this paper
• Linear Kernels on Graphs Excluding Topological Minors

  2012cites this paper
• Linear Problem Kernels for Planar Graph Problems with Small Distance Property

  2011cites this paper
• A linear kernel for planar connected dominating set

  2011cites this paper
• On the directed Full Degree Spanning Tree problem

  2011cites this paper
• Bidimensionality and kernels

  2010cites this paper
• PARAMETERIZING FROM THE EXTREMES: FEASIBLE PARAMETERIZATIONS OF SOME NP-OPTIMIZATION PROBLEMS

  2010cites this paper
• Algorithms in moderately exponential time

  2010cites this paper
• The parameterized complexity of the induced matching problem

  2009cites this paper
• (Meta) Kernelization

  2009influential citation
• Kernelization: New Upper and Lower Bound Techniques

  2009cites this paper
• On the Directed Degree-Preserving Spanning Tree Problem

  2009cites this paper
• Linear Kernel for Planar Connected Dominating Set

  2009cites this paper
• New Methods in Parameterized Algorithms and Complexity

  2009cites this paper
• A Moderately Exponential Time Algorithm for Full Degree Spanning Tree

  2008cites this paper
• Introduction to Complexity Theory Column 54

  2008cites this paper
• Data Reduction for Domination in Graphs

  2008cites this paper