Structural parameterizations of the biclique-free vertex deletion problem

DOI10.46298/DMTCS.13018MaRDI QIDQ6986998zbMATH OpenFDO

Authors Lito Goldmann, Leon Kellerhals, Tomohiro Koana

Publication date 7 May 2025

Published in Discrete Mathematics and Theoretical Computer Science. DMTCS (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.46298/DMTCS.13018

zbMATH Keywords

biclique-free graphsfixed-parameter tractabilitykernelizationstructural graph parameterizations

Mathematics Subject Classification ID

Vertex degrees (05C07) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) Social networks; opinion dynamics (91D30)

Cites work

• A generalization of Nemhauser and Trotter's local optimization theorem
• A graph‐theoretic generalization of the clique concept
• A linear kernel for co-path/cycle packing
• Approximation algorithms for finding and partitioning unit-disk graphs into co-k-plexes
• Arboricity and bipartite subgraph listing algorithms
• Clique relaxations in social network analysis: the maximum k-plex problem
• Combinatorial algorithms for the maximum \(k\)-plex problem
• Computing dense and sparse subgraphs of weakly closed graphs
• Covering many (or few) edges with \(k\) vertices in sparse graphs
• Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
• Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
• FPT algorithms for domination in sparse graphs and beyond
• Fundamentals of parameterized complexity
• Graph theory
• Grundy Coloring and friends, half-graphs, bicliques
• scientific article; zbMATH DE number 1354124 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Immersions in highly edge connected graphs
• Isolation concepts for efficiently enumerating dense subgraphs
• Length-bounded cuts: proper interval graphs and structural parameters
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Lossy kernels for connected dominating set on sparse graphs
• On bounded-degree vertex deletion parameterized by treewidth
• On structural parameterizations of the bounded-degree vertex deletion problem
• Parameterized algorithms
• Parameterized Algorithms for Generalized Domination
• Parameterized Complexity for Domination Problems on Degenerate Graphs
• Parameterized complexity of geodetic set
• Parameterized complexity of length-bounded cuts and multicuts
• Progressive algorithms for domination and independence
• Reconfiguration on sparse graphs
• Reduction algorithms for graphs of small treewidth
• Structural parameterizations for two bounded degree problems revisited
• The (weighted) metric dimension of graphs: hard and easy cases
• The mixed Chinese postman problem parameterized by pathwidth and treedepth
• The parameterized complexity of the k-biclique problem
• Tree-depth, subgraph coloring and homomorphism bounds

This page was built for publication: Structural parameterizations of the biclique-free vertex deletion problem

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