Cover Image

Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bieliński, Paweł Rafał, Piecyk, Marta, Rzążewski, Paweł
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Kernelization for list $H$-coloring for graphs with small vertex cover
by: Piecyk, Marta, et al.
Published: (2025)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
by: Dvořák, Pavel, et al.
Published: (2022)

Max Weight Independent Set in sparse graphs with no long claws
by: Abrishami, Tara, et al.
Published: (2023)

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
by: Gartland, Peter, et al.
Published: (2023)

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)

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

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

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
by: Esmer, Barış Can, et al.
Published: (2024)

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

A Comprehensive Survey of Data Reduction Rules for the Maximum Weighted Independent Set Problem
by: Großmann, Ernestine, et al.
Published: (2024)

Finding Maximum Weight 2-Packing Sets on Arbitrary Graphs
by: Borowitz, Jannick, et al.
Published: (2025)

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

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
by: Lokshtanov, Daniel, et al.
Published: (2024)

On the complexity of edge subdivision to $H$-free graphs
by: Piecyk, Marta, et al.
Published: (2026)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
by: Esmer, Barış Can, et al.
Published: (2022)

Optimal Distance Labeling for Permutation Graphs
by: Gawrychowski, Paweł, et al.
Published: (2024)

Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs
by: Chaplick, Steven, et al.
Published: (2024)

Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs
by: Gil, Yuval
Published: (2024)

Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs
by: Großmann, Ernestine, et al.
Published: (2026)

Maximum Independent Sets in Disk Graphs with Disks in Convex Position
by: Tkachenko, Anastasiia, et al.
Published: (2026)

Distributed Reductions for the Maximum Weight Independent Set Problem
by: Borowitz, Jannick, et al.
Published: (2025)

Learning-augmented Maximum Independent Set
by: Braverman, Vladimir, et al.
Published: (2024)

Enumerating m-Length Walks in Directed Graphs with Constant Delay
by: Adamson, Duncan, et al.
Published: (2024)

Parameterized Complexity of Directed Traveling Salesman Problem
by: Blažej, Václav, et al.
Published: (2025)

A Faster Algorithm for Maximum Weight Matching on Unrestricted Bipartite Graphs
by: Kwok, Shawxing
Published: (2025)

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
by: Bernstein, Aaron, et al.
Published: (2025)

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
by: Ghoshal, Suprovat, et al.
Published: (2026)

Enumerating All Directed Spanning Trees in Optimal Time
by: Gawrychowski, Paweł, et al.
Published: (2026)

Better Indexing for Rectangular Pattern Matching
by: Gawrychowski, Paweł, et al.
Published: (2025)

Approximating the shortest path problem with scenarios
by: Kasperski, Adam, et al.
Published: (2018)

Faster CONGEST Approximation Algorithms for Maximum Weighted Independent Set in Sparse Graphs
by: Faour, Salwa, et al.
Published: (2025)

An $11/6$-Approximation Algorithm for Vertex Cover on String Graphs
by: Bonnet, Édouard, et al.
Published: (2024)

Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
by: Adar, Tomer, et al.
Published: (2026)

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
by: Kothari, Pravesh, et al.
Published: (2024)

Triangle-Covered Graphs: Algorithms, Complexity, and Structure
by: Madani, Amirali, et al.
Published: (2025)

Approximation Algorithms for Connected Maximum Coverage, Minimum Connected Set Cover, and Node-Weighted Group Steiner Tree
by: D'Angelo, Gianlorenzo, et al.
Published: (2025)

Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications
by: Gawrychowski, Paweł, et al.
Published: (2024)

Dynamic Longest Common Substring in Polylogarithmic Time
by: Charalampopoulos, Panagiotis, et al.
Published: (2020)

Equivalences between Non-trivial Variants of 3LDT and Conv3LDT
by: Dudek, Bartłomiej, et al.
Published: (2020)

Recoverable robust shortest path problem under interval budgeted uncertainty representations
by: Jackiewicz, Marcel, et al.
Published: (2024)