Vertex identification to a forest

DOI10.1016/J.DISC.2025.114699MaRDI QIDQ6930277zbMATH OpenFDO

Authors Laure Morelle, Ignasi Sau, Dimitrios M. Thilikos

Publication date 16 September 2025

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DISC.2025.114699

zbMATH Keywords

graph minorsvertex coverkernelizationparameterized algorithmsvertex identificationuniversal obstructions

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites work

• scientific article; zbMATH DE number 1543076 (Why is no real title available?)
• scientific article; zbMATH DE number 1554933 (Why is no real title available?)
• A 2k-kernelization algorithm for vertex cover based on crown decomposition
• A survey of parameterized algorithms and the complexity of edge modification
• Compound logics for modification problems
• Contracting graphs to paths and trees
• Edge-Deletion Problems
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XX: Wagner's conjecture
• Graph minors. XXI. graphs with unique linkages
• Graph minors. XXII. Irrelevant vertices in linkage problems
• Graph theory
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Modification to Planarity is Fixed Parameter Tractable
• Obtaining a bipartite graph by contracting few edges
• On Independent Circuits Contained in a Graph
• Parameterized and Exact Computation
• Parameterized complexity of biclique contraction and balanced biclique contraction
• Properties of vertex cover obstructions
• Split contraction: the untold story
• The complexity of surjective homomorphism problems-a survey
• The disjoint paths problem in quadratic time
• The node-deletion problem for hereditary properties is NP-complete
• Vertex fusion under distance constraints
• Vertex packings: Structural properties and algorithms

Cited in

(1)

• On the polynomial kernelizations of finding a shortest path with positive disjunctive constraints

This page was built for publication: Vertex identification to a forest

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6930277)