Linear‐time algorithms for eliminating claws in graphs
From MaRDI portal
Publication:6082274
DOI10.1111/itor.13100OpenAlexW4200203203MaRDI QIDQ6082274
Fabiano S. Oliveira, Jayme Luiz Szwarcfiter, Uéverton S. Souza, Julliano Rosa Nascimento, Flavia Bonomo-Braberman
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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding and counting small induced subgraphs efficiently
- Dominating set is fixed parameter tractable in claw-free graphs
- On Hamiltonian claw-free graphs
- Graph minors. III. Planar tree-width
- Parameterized algorithms for \(d\)-hitting set: the weighted case
- The node-deletion problem for hereditary properties is NP-complete
- All structured programs have small tree width and good register allocation
- A partial k-arboretum of graphs with bounded treewidth
- Treewidth. Computations and approximations
- Claw-free graphs---a survey
- Which problems have strongly exponential complexity?
- Vertex deletion problems on chordal graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Powers of tensors and fast matrix multiplication
- On the power of unique 2-prover 1-round games
- Node-Deletion Problems on Bipartite Graphs
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Graphs with 1-Factors
- Finding Four-Node Subgraphs in Triangle Time
- Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
- The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ 1
- Depth-First Search and Linear Graph Algorithms
- On the complexity of \(k\)-SAT
This page was built for publication: Linear‐time algorithms for eliminating claws in graphs
