On Generating Triangle-Free Graphs
From MaRDI portal
Publication:2839211
DOI10.1016/j.endm.2009.02.008zbMath1267.05246OpenAlexW2081072149MaRDI QIDQ2839211
Christian Komusiewicz, Daniel Brügmann, Hannes Moser
Publication date: 4 July 2013
Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.endm.2009.02.008
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (19)
Parameterizing edge modification problems above lower bounds ⋮ Polynomial kernelization for removing induced claws and diamonds ⋮ Two edge modification problems without polynomial kernels ⋮ Kernel for \(K_t\)\textsc{-free Edge Deletion} ⋮ On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion} ⋮ Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Cutting a tree with subgraph complementation is hard, except for some small trees ⋮ Kernelization for cycle transversal problems ⋮ The parameterized complexity and kernelization of resilience for database queries ⋮ On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems ⋮ On the small cycle transversal of planar graphs ⋮ On the Small Cycle Transversal of Planar Graphs ⋮ New kernels for several problems on planar graphs ⋮ Feedback edge sets in temporal graphs ⋮ Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal ⋮ Triangle edge deletion on planar glasses-free RGB-digraphs ⋮ Two Edge Modification Problems without Polynomial Kernels ⋮ A balm: defend the clique-based attack from a fundamental aspect
Cites Work
- Unnamed Item
- Finding and counting given length cycles
- Automated generation of search tree algorithms for hard graphs modification problems
- A Problem Kernelization for Graph Packing
- Kernelization Algorithms for d-Hitting Set Problems
- Edge-Deletion Problems
- Approximating Maximum Subgraphs without Short Cycles
This page was built for publication: On Generating Triangle-Free Graphs
