Paths to trees and cacti

DOI10.1007/978-3-319-57586-5_4MaRDI QIDQ5283353zbMATH OpenOpenAlexFDO

Authors Akanksha Agrawal, Lawqueen Kanesh, Saket Saurabh, Prafullkumar Tale

Publication date 21 July 2017

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

Full work available at URL https://doi.org/10.1007/978-3-319-57586-5_4

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Paths to trees and cacti
• On the parameterized complexity of contraction to generalization of trees
• On the parameterized complexity of contraction to generalization of trees

Cites work

• A Subexponential Parameterized Algorithm for Proper Interval Completion
• A subexponential parameterized algorithm for proper interval completion
• Chordal deletion is fixed-parameter tractable
• Chordal editing is fixed-parameter tractable
• Contracting few edges to remove forbidden induced subgraphs
• Edge-contraction problems
• Exploring subexponential parameterized complexity of completion problems
• Faster parameterized algorithms for deletion to split graphs
• Finding odd cycle transversals.
• Fixed-parameter tractability of graph modification problems for hereditary properties
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Interval deletion is fixed-parameter tractable
• Linear recognition of almost interval graphs
• Obtaining a bipartite graph by contracting few edges
• Obtaining planarity by contracting few edges
• On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges
• On the NP-hardness of edge-deletion and -contraction problems
• On the removal of forbidden graphs by edge-deletion or by edge- contraction
• Parameterized algorithms
• Parameterized complexity of vertex deletion into perfect graph classes
• Sparsification upper and lower bounds for graphs problems and not-all-equal SAT
• Subexponential parameterized algorithm for minimum fill-in
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters

Cited in

(14)

• An FPT algorithm for contraction to cactus
• Paths to trees and cacti
• On the parameterized complexity of contraction to generalization of trees
• Parameterized complexity of maximum edge colorable subgraph
• An improved linear kernel for the cycle contraction problem
• On the parameterized complexity of grid contraction
• A single exponential-time FPT algorithm for cactus contraction
• Path contraction faster than 2ⁿ
• Trees, Paths, Stars, Caterpillars and Spiders
• Lossy kernels for graph contraction problems
• On the parameterized complexity of contraction to generalization of trees
• Contracting to a longest path in H-free graphs
• On the Parameterized Complexity of Maximum Degree Contraction Problem.
• On the parameterized complexity of maximum degree contraction problem

This page was built for publication: Paths to trees and cacti

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