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

DOI10.1007/978-3-030-86838-3_6OpenAlexW3202334902MaRDI QIDQ2672425FDOQ2672425

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

Publication date: 8 June 2022

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

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
• A faster FPT algorithm for bipartite contraction
• A faster FPT algorithm for bipartite contraction
• FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs

zbMATH Keywords

FPTodd cycle transversalelimination distance

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

• Backdoor DNFs
• Faster FPT algorithms for deletion to pairs of graph classes
• Title not available (Why is that?)
• Distance from triviality 2.0: hybrid parameterizations
• Deletion to scattered graph classes. I: Case of finite number of graph classes

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)