Approximation algorithms for intersection graphs
type: Item
instance of: scholarly article
title: Approximation algorithms for intersection graphs
zbMATH Open document ID: 1303.05193
author: Frank Kammer
author: Torsten Tholey
published in: Algorithmica
publication date: 2014-12-02T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C22
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C76
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6375631
zbMATH Keywords: intersection graphs
zbMATH Keywords: parameterized approximation algorithms
zbMATH Keywords: graph algorithms
zbMATH Keywords: NP-hard problems
MaRDI profile type: Publication
full work available at URL: s00453-012-9671-1
OpenAlex ID: W2081642180
Wikidata QID: Q56019096
cites work: Q4459826
cites work: Scheduling Split Intervals
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: Optimization problems in multiple-interval graphs
cites work: Q5708492
cites work: Polynomial-time approximation schemes for packing and piercing fat objects
cites work: Unit disk graphs
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Q4503944
cites work: Minimum clique partition in unit disk graphs
cites work: Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
cites work: Domination in Geometric Intersection Graphs
cites work: Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function
cites work: Parametrized complexity theory.
cites work: Optimal packing and covering in the plane are NP-complete
cites work: Q4093489
cites work: Some simplified NP-complete graph problems
cites work: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
cites work: Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
cites work: Q3328583
cites work: Algorithmic aspects of intersection graphs and representation hypergraphs
cites work: Extremal Values of the Interval Number of a Graph
cites work: NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
cites work: Approximating minimum independent dominating sets in wireless networks
cites work: Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
cites work: Tolerance intersection graphs on binary trees with constant tolerance 3
cites work: Parameterized Complexity in Multiple-Interval Graphs: Partition, Separation, Irredundancy
cites work: Approximation Algorithms for Intersection Graphs
cites work: Optimization, approximation, and complexity classes
cites work: Simple heuristics for unit disk graphs
cites work: Approximation schemes for wireless networks
cites work: Q5710169
cites work: A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
cites work: Q4161356
cites work: A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
cites work: Elimination Graphs
cites work: Q3002782
DOI: 10.1007/S00453-012-9671-1
description: scientific article; zbMATH DE number 6375631