scientific article; zbMATH DE number 7651162

DOI10.4230/LIPICS.ESA.2020.23MaRDI QIDQ5874491FDOQ5874491

Stéphan Thomassé, Édouard Bonnet, Xuan Thang Tran, Rémi Watrigant

Publication date: 7 February 2023

Full work available at URL: https://arxiv.org/abs/2004.12166

Title of this publication is not available (Why is that?)

Recommendations

• scientific article
• On Erdös-Gallai and Havel-Hakimi algorithms
• A Weakening of the Odd Hadwiger's Conjecture
• The Erdős-Hajnal conjecture. A survey
• scientific article
• Algorithmic aspects of Suslin's proof of Serre's conjecture
• A survey and strengthening of Erdős-Gyarfas conjecture
• A strengthening of the Erdős-Szekeres theorem
• On Helly's theorem: Algorithms and extensions
• An algorithm for Komlós conjecture matching Banaszczyk's bound

zbMATH Keywords

approximationmaximum independent set\(H\)-free graphsErdő's-Hajnal conjecture

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Geometric algorithms and combinatorial optimization
• Some APX-completeness results for cubic graphs
• The Erdős-Hajnal conjecture. A survey
• Title not available (Why is that?)
• Approximation algorithms for NP-complete problems on planar graphs
• Some remarks on the theory of graphs
• Improved results on geometric hitting set problems
• The Ramsey number R(3, t) has order of magnitude t²/log t
• On maximal independent sets of vertices in claw-free graphs
• A note on Ramsey numbers
• Title not available (Why is that?)
• Title not available (Why is that?)
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• On the size of a random maximal graph
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Sparse graphs: Metrics and random models
• Ramsey-type theorems
• Graph Theory and Probability. II
• Bounding Ramsey numbers through large deviation inequalities
• Polynomial-time approximation schemes for packing and piercing fat objects
• Computing independent sets in graphs with large girth
• Approximation algorithms for maximum independent set of pseudo-disks
• Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs
• Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time
• Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
• Title not available (Why is that?)

Cited In (8)

• Algorithmic aspects of Suslin's proof of Serre's conjecture
• A Weakening of the Odd Hadwiger's Conjecture
• Title not available (Why is that?)
• Parameterized inapproximability of independent set in \(H\)-free graphs
• A lower bound for weak Schur numbers with a deterministic algorithm
• Title not available (Why is that?)
• Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
• An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture

This page was built for publication:

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