Approximation of MWIS on geometric intersection graphs

DOI10.1016/J.COMGEO.2025.102228MaRDI QIDQ6873626zbMATH OpenFDO

Authors C. R. Subramanian

Publication date 16 January 2026

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.COMGEO.2025.102228

zbMATH Keywords

approximation algorithmsgeometric intersection graphsindependent sets

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cites work

• A 3-approximation algorithm for maximum independent set of rectangles
• Algorithmic graph theory and perfect graphs
• An algorithm for the maximum weight independent set problem on outerstring graphs
• Approximating maximum independent set for rectangles in the plane
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation schemes for maximum weight independent set of rectangles
• Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
• Coloring and Maximum Weight Independent Set of Rectangles
• Decomposition by clique separators
• Efficient algorithms for interval graphs and circular-arc graphs
• Finding a maximum independent set in a permutation graph
• Geometric algorithms and combinatorial optimization
• Inductive graph invariants and approximation algorithms
• Interval representations of planar graphs
• Label placement by maximum independent set in rectangles
• Maximum independent set for intervals by divide and conquer with pruning
• Maximum independent set of rectangles
• Maximum independent set on \(B_1\)-VPG graphs
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• On approximating maximum independent set of rectangles
• On approximating MIS over B1-VPG graphs*
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Space graphs and sphericity
• Splitting \(B_2\)-VPG graphs into outer-string and co-comparability graphs
• The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
• Vertex Intersection Graphs of Paths on a Grid

This page was built for publication: Approximation of MWIS on geometric intersection graphs

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