FPT algorithms to compute the elimination distance to bipartite graphs and more

DOI10.1007/978-3-030-86838-3_6MaRDI QIDQ2672425zbMATH OpenOpenAlexFDO

Authors Bart M. P. Jansen, Jari J. H. de Kroon

Publication date 8 June 2022

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2106.04191

zbMATH Keywords

elimination distanceFPTodd cycle transversal

Mathematics Subject Classification ID

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

Recommendations

• A fixed-parameter tractable algorithm for elimination distance to bounded degree graphs
• FPT algorithms for domination in biclique-free graphs
• An FPT algorithm for bipartite vertex splitting
• Faster FPT algorithms for deletion to pairs of graph classes
• On distance-preserving elimination orderings in graphs: complexity and algorithms
• FPT algorithms for domination in sparse graphs and beyond
• Algorithmic aspects of bipartite graphs
• FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs

Cites work

• A faster parameterized algorithm for treedepth
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Combining treewidth and backdoors for CSP
• Elimination Distance to Bounded Degree on Planar Graphs
• Elimination distances, blocking sets, and kernels for Vertex Cover
• Finding odd cycle transversals.
• Fixed-parameter tractable distances to sparse graph classes
• Fundamentals of parameterized complexity
• Graph Classes: A Survey
• Graph isomorphism parameterized by elimination distance to bounded degree
• Graph Layout Problems Parameterized by Vertex Cover
• Graph minors. XIII: The disjoint paths problem
• Graph structure and monadic second-order logic. A language-theoretic approach
• Isomorphism for graphs of bounded feedback vertex set number
• Measuring what matters: a hybrid approach to dynamic programming with treewidth
• Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs
• On the Parameterized Complexity of Clique Elimination Distance
• Parameterized algorithms
• Parameterized and Exact Computation
• Reducing CMSO model checking to highly connected graphs
• Sparsity. Graphs, structures, and algorithms
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth computation and extremal combinatorics
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Vertex deletion parameterized by elimination distance and even less

Cited in

(9)

• Faster FPT algorithms for deletion to pairs of graph classes
• Distance from triviality 2.0: hybrid parameterizations
• scientific article; zbMATH DE number 7204399 (Why is no real title available?)
• Deletion to scattered graph classes. I: Case of finite number of graph classes
• Backdoor DNFs
• Dynamic programming on bipartite tree decompositions
• Dynamic programming on bipartite tree decompositions
• FPT approximations for packing and covering problems parameterized by elimination distance and even less
• Preprocessing to reduce the search space for odd cycle transversal

This page was built for publication: FPT algorithms to compute the elimination distance to bipartite graphs and more

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