On Generating Triangle-Free Graphs

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

zbMATH Keywords

kernelizationNP-complete problemparameterized algorithmics

Mathematics Subject Classification ID

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