Complexity of independency and cliquy trees

DOI10.1016/j.dam.2018.08.011zbMath1429.05036OpenAlexW2898583977WikidataQ59864851 ScholiaQ59864851MaRDI QIDQ2283099

Katrin Casel, Jan Dreier, Markus L. Schmid, Moritz Gobbert, Fernando Sánchez Villaamil, Philipp Kuinke, Henning Fernau, Erik Jan van Leeuwen

Publication date: 30 December 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2018.08.011

zbMATH Keywords

parameterized complexityexact algorithmskernelization algorithmsindependency treecliquy tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Scatter search for the minimum leaf spanning tree problem ⋮ Extension and its price for the connected vertex cover problem

Cites Work

• Fundamentals of parameterized complexity
• Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
• On miniaturized problems in parameterized complexity theory
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• FPT algorithms and kernels for the directed \(k\)-leaf problem
• Approximating the maximum internal spanning tree problem
• On finding optimal and near-optimal lineal spanning trees
• Complexity of spanning tree problems: Part I
• NP-completeness and degree restricted spanning trees
• Spanning trees with pairwise nonadjacent endvertices
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• Better approximation algorithms for the maximum internal spanning tree problem
• Deterministic Parameterized Connected Vertex Cover
• The regenerator location problem
• Vulnerability bounds on the number of spanning tree leaves
• Hamilton Paths in Grid Graphs
• Kernelization Lower Bounds Through Colors and IDs
• Parameterized Algorithms
• The steiner problem in graphs
• Algorithms and Data Structures
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity of independency and cliquy trees