Cover Image

Max Weight Independent Set in sparse graphs with no long claws

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Abrishami, Tara, Chudnovsky, Maria, Dibek, Cemil, Pilipczuk, Marcin, Rzążewski, Paweł
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
by: Majewski, Konrad, et al.
Published: (2022)

Graphs with no long claws: An improved bound for the analog of the Gyárfás' path argument
by: Bourneuf, Romain, et al.
Published: (2025)

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs
by: Marx, Dániel, et al.
Published: (2026)

Bounding $\varepsilon$-scatter dimension via metric sparsity
by: Bourneuf, Romain, et al.
Published: (2024)

Coarse Balanced Separators in Fat-Minor-Free Graphs
by: Bonnet, Édouard, et al.
Published: (2026)

Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs
by: Bencs, Ferenc, et al.
Published: (2025)

Tree Independence Number IV. Even-hole-free Graphs
by: Chudnovsky, Maria, et al.
Published: (2024)

Weighted Clique and Independent Set in Edge-Distant Hereditary Graphs
by: Srinivasan, Eshwar, et al.
Published: (2026)

Induced Cycles of Many Lengths
by: Chudnovsky, Maria, et al.
Published: (2026)

Independent set reconfiguration in H-free graphs
by: Bartier, Valentin, et al.
Published: (2024)

Subexponential and Parameterized Mixing Times of Glauber Dynamics on Independent Sets
by: Marin, Malory
Published: (2025)

QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes
by: Bonnet, Édouard, et al.
Published: (2026)

Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees
by: Efthymiou, Charilaos, et al.
Published: (2023)

Elementary first-order model checking for sparse graphs
by: Gajarský, Jakub, et al.
Published: (2024)

Stable Approximation Algorithms for Dominating Set and Independent Set
by: de Berg, Mark, et al.
Published: (2024)

Designing sparse temporal graphs satisfying connectivity requirements
by: Bellitto, Thomas, et al.
Published: (2026)

Minsum Problem for Discrete and Weighted Set Flow on Dynamic Path Network
by: Manna, Bubai, et al.
Published: (2024)

Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs
by: Deák, Bence, et al.
Published: (2026)

Feedback Vertex Set for pseudo-disk graphs in subexponential FPT time
by: Berthe, Gaétan, et al.
Published: (2024)

Sparse induced subgraphs in $P_7$-free graphs of bounded clique number
by: Chudnovsky, Maria, et al.
Published: (2024)

Induced Minors and Coarse Tree Decompositions
by: Chudnovsky, Maria, et al.
Published: (2026)

A Polynomial Coreset for Furthest Neighbor in Planar Metrics
by: Kluk, Kacper, et al.
Published: (2026)

Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
by: Lokshtanov, Daniel, et al.
Published: (2026)

Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity
by: Gawrychowski, Paweł, et al.
Published: (2024)

Approximation Algorithms for the $b$-Matching and List-Restricted Variants of MaxQAP
by: Nanta, Jiratchaphat, et al.
Published: (2025)

Edge Clique Partition and Cover Beyond Independence
by: Fomin, Fedor V., et al.
Published: (2025)

Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
by: Fomin, Fedor V., et al.
Published: (2024)

Variants of Merge-Width and Applications
by: Drabik, Karolina, et al.
Published: (2026)

Node-Weighted Triangles: Faster and Simpler
by: Akmal, Shyan, et al.
Published: (2026)

Graph classes through the lens of logic
by: Pilipczuk, Michał
Published: (2025)

Tight Localizations of Feedback Sets
by: Hecht, Michael, et al.
Published: (2020)

Improved bounds for coloring locally sparse hypergraphs
by: Iliopoulos, Fotis
Published: (2020)

Greedy Algorithms for Shortcut Sets and Hopsets
by: Bals, Ben, et al.
Published: (2025)

Parameterized Complexity of Path Set Packing
by: Aravind, N. R., et al.
Published: (2022)

Tight Paths and Tight Pairs in Weighted Directed Graphs
by: Balcázar, José Luis
Published: (2025)

Minimum Sum Set Cover: Structures and Algorithm
by: Zhang, Zhongyi, et al.
Published: (2026)

Partially Ordered Sets Corresponding to the Partition Problem
by: Kubo, Susumu
Published: (2024)

Circular-arc graphs and the Helly property
by: Derbisz, Jan, et al.
Published: (2024)

The Complexity of Diameter on H-free graphs
by: Oostveen, Jelle J., et al.
Published: (2024)

Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
by: Foucaud, Florent, et al.
Published: (2026)