Algorithms and Data Structures

DOI10.1007/b11837zbMath1278.68109MaRDI QIDQ5900777

Elena Prieto, Christian Sloper

Publication date: 20 April 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

zbMATH Keywords

vertex cover; fixed-parameter tractability; kernelization; spanning trees

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

A Polynomial Time Algorithm for Finding a Spanning Tree with Maximum Number of Internal Vertices on Interval Graphs, Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem, Approximation algorithms for the maximum weight internal spanning tree problem, On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves, Improved upper bounds for vertex cover, Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree, The complexity ecology of parameters: An illustration using bounded max leaf number, A parameterized perspective on packing paths of length two, Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem, Minimum leaf out-branching and related problems, An approximation algorithm for maximum internal spanning tree, Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}, Algorithms for maximum internal spanning tree problem for some graph classes, Scatter search for the minimum leaf spanning tree problem, A simple linear time algorithm to solve the MIST problem on interval graphs, Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs, Complexity of independency and cliquy trees, Crown reductions for the minimum weighted vertex cover problem, Solving the maximum internal spanning tree problem on interval graphs in polynomial time, A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem, Unnamed Item, Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems, Improved Approximations for Hard Optimization Problems via Problem Instance Classification, Structural Properties of Hard Metric TSP Inputs, Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem, A 2k-vertex Kernel for Maximum Internal Spanning Tree