Linear‐time algorithms for eliminating claws in graphs

DOI10.1111/ITOR.13100MaRDI QIDQ6082274zbMATH OpenOpenAlexFDO

Authors Flavia Bonomo, Julliano Rosa Nascimento, Fabiano S. Oliveira, Uéverton S. Souza, Jayme L. Szwarcfiter

Publication date 29 November 2023

Published in International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1111/itor.13100

zbMATH Keywords

claw-free graphvertex deletionweighted vertex deletion

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Cites work

• A c^k n 5-approximation algorithm for treewidth
• A partial k-arboretum of graphs with bounded treewidth
• All structured programs have small tree width and good register allocation
• Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Claw-free graphs---a survey
• Depth-First Search and Linear Graph Algorithms
• Dominating set is fixed parameter tractable in claw-free graphs
• Finding and counting small induced subgraphs efficiently
• Finding four-node subgraphs in triangle time
• Graph minors. III. Planar tree-width
• Graphs with 1-Factors
• scientific article; zbMATH DE number 4085681 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• Linear time solvable optimization problems on graphs of bounded clique-width
• Node-Deletion Problems on Bipartite Graphs
• On Hamiltonian claw-free graphs
• On the complexity of k-SAT
• On the power of unique 2-prover 1-round games
• Parameterized algorithms for d-hitting set: the weighted case
• Parametrized complexity theory.
• Powers of tensors and fast matrix multiplication
• Solving the weighted stable set problem in claw-free graphs via decomposition
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The node-deletion problem for hereditary properties is NP-complete
• The structure of claw-free graphs
• The unique games conjecture, integrality gap for cut problems and embeddability of negative-type metrics into _1
• Treewidth. Computations and approximations
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Vertex deletion problems on chordal graphs
• Which problems have strongly exponential complexity?

Cited in

(1)

• Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes

This page was built for publication: Linear‐time algorithms for eliminating claws in graphs

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