Journal of Combinatorial Optimization

Journal: Journal of Combinatorial Optimization

Abbreviation

J Comb Optim

Publisher

Springer

ISSN

1382-6905
1573-2886

Show all metadata

Search Results

Publications 1 - 6 of 6

Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem
D’Emidio, Mattia; Forlizzi, Luca; Frigioni, Daniele; et al. (2019)
Journal of Combinatorial Optimization
Single machine batch scheduling with release times
Gfeller, Beat; Peeters, Leon; Weber, Birgitta; et al. (2009)
Journal of Combinatorial Optimization
Sum-of-squares rank upper bounds for matching problems
Kurpisz, Adam; Leppänen, Samuli; Mastrolilli, Monaldo (2018)
Journal of Combinatorial Optimization
Convex partitions with 2-edge connected dual graphs
Al-Jubeh, Marwan; Hoffmann, Michael; Ishaque, Mashhood; et al. (2011)
Journal of Combinatorial Optimization
Alignments with non-overlapping moves, inversions and tandem duplications in O(n4) time
Ledergerber, Christian; Dessimoz, Christophe (2008)
Journal of Combinatorial Optimization
Computing a maximum clique in geometric superclasses of disk graphs
Grelier, Nicolas (2022)
Journal of Combinatorial Optimization
In the 90's Clark, Colbourn and Johnson wrote a seminal paper where they proved that maximum clique can be solved in polynomial time in unit disk graphs. Since then, the complexity of maximum clique in intersection graphs of d-dimensional (unit) balls has been investigated. For ball graphs, the problem is NP-hard, as shown by Bonamy et al. (FOCS '18). They also gave an efficient polynomial time approximation scheme (EPTAS) for disk graphs. However, the complexity of maximum clique in this setting remains unknown. In this paper, we show the existence of a polynomial time algorithm for a geometric superclass of unit disk graphs. Moreover, we give partial results toward obtaining an EPTAS for intersection graphs of convex pseudo-disks.

Publications 1 - 6 of 6

Journal: Journal of Combinatorial Optimization

Abbreviation

Publisher

Journal Volumes

ISSN

Description

Filters

Search Results