Improved (In-)Approximability Bounds for d-Scattered Set
From MaRDI portal
Publication:6107026
DOI10.7155/jgaa.00621zbMath1518.05049OpenAlexW2979914281MaRDI QIDQ6107026
Vangelis Th. Paschos, Michael Lampis, Ioannis Katsikarelis
Publication date: 3 July 2023
Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.7155/jgaa.00621
Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- On the model-checking of monadic second-order formulas with edge set quantifications
- Spectra of graphs
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Automata, languages and programming. 26th international colloquium, ICALP `99. Prague, Czech Republic, July 11--15, 1999. Proceedings
- Improved approximations for maximum independent set via approximation chains
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Which problems have strongly exponential complexity?
- Time-approximation trade-offs for inapproximable problems
- Derandomized graph products
- Independent sets with domination constraints
- Structurally parameterized \(d\)-scattered set
- Improved (In-)approximability bounds for \(d\)-scattered set
- Distance-\(d\) independent set problems for bipartite and chordal graphs
- Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs
- Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs
- Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs
- On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators
- Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
- The Diameter of a Cycle Plus a Random Matching
- Approximation algorithms for NP-complete problems on planar graphs
- On the complexity of \(k\)-SAT
