Document Search Results

Chalermsook, Parinya; Gadekar, Ameet; Khodamoradi, Kamyar; Spoerhase, Joachim

Independent set in \(k\)-claw-free graphs: conditional \(\chi \)-boundedness and the power of LP/SDP relaxations. (English) Zbl 07883489

Byrka, Jarosław (ed.) et al., Approximation and online algorithms. 21st international workshop, WAOA 2023, Amsterdam, The Netherlands, September 7–8, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 14297, 205-218 (2023).

MSC: 68W25 68W27

Cite Review PDF

Full Text: DOI arXiv

Bhore, Sujoy; Haunert, Jan-Henrik; Klute, Fabian; Li, Guangping; Nöllenburg, Martin

Balanced independent and dominating sets on colored interval graphs. (English) Zbl 1490.68147

Bureš, Tomáš (ed.) et al., SOFSEM 2021: theory and practice of computer science. 47th international conference on current trends in theory and practice of computer science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25–29, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12607, 89-103 (2021).

MSC: 68R10 05C69 68Q17 68Q27 68W25

Cite Review PDF

Full Text: DOI arXiv

Berndt, Sebastian; Grage, Kilian; Jansen, Klaus; Johannsen, Lukas; Kosche, Maria

Robust online algorithms for dynamic choosing problems. (English) Zbl 07495154

De Mol, Liesbeth (ed.) et al., Connecting with computability. 17th conference on computability in Europe, CiE 2021, virtual event, Ghent, Belgium, July 5–9, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12813, 38-49 (2021).

MSC: 68Qxx

Cite Review PDF

Full Text: DOI arXiv

Le, Hung; Zheng, Baigong

Local search is a PTAS for feedback vertex set in minor-free graphs. (English) Zbl 1461.68157

Theor. Comput. Sci. 838, 17-24 (2020).

MSC: 68R10 68W25

Cite Review PDF

Full Text: DOI arXiv

Agarwal, Pankaj K.; Pan, Jiangwei

Near-linear algorithms for geometric hitting sets and set covers. (English) Zbl 1448.68445

Discrete Comput. Geom. 63, No. 2, 460-482 (2020).

MSC: 68U05 52C17 68W05 68W20 68W25 68W40

Cite Review PDF

Full Text: DOI

Le, Hung; Zheng, Baigong

A simple local search gives a PTAS for the feedback vertex set problem in minor-free graphs. (English) Zbl 1534.68181

Du, Ding-Zhu (ed.) et al., Computing and combinatorics. 25th international conference, COCOON 2019, Xi’an, China, July 29–31, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11653, 375-386 (2019).

MSC: 68R10 68Q25 68W25 90C59

Cite Review PDF

Full Text: DOI

Chaplick, Steven; De, Minati; Ravsky, Alexander; Spoerhase, Joachim

Approximation schemes for geometric coverage problems. (English) Zbl 1522.68636

Azar, Yossi (ed.) et al., 26th annual European symposium on algorithms, ESA 2018, August 20–22, 2018, Helsinki, Finland. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 112, Article 17, 15 p. (2018).

MSC: 68U05 68W25

Cite Review PDF

Full Text: DOI arXiv

Li, Xiaosong; Shi, Yishuo; Huang, Xiaohui

PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs. (English) Zbl 1382.05037

Discrete Appl. Math. 239, 119-124 (2018).

MSC: 05C35 05C70 05C40

Cite Review PDF

Full Text: DOI

Ene, Alina; Har-Peled, Sariel; Raichel, Benjamin

Geometric packing under nonuniform constraints. (English) Zbl 1380.68393

SIAM J. Comput. 46, No. 6, 1745-1784 (2017).

MSC: 68U05 68Q25 68W25

Cite Review PDF

Full Text: DOI arXiv

Bus, Norbert; Garg, Shashwat; Mustafa, Nabil H.; Ray, Saurabh

Limits of local search: quality and efficiency. (English) Zbl 1369.68339

Discrete Comput. Geom. 57, No. 3, 607-624 (2017).

MSC: 68U05 68T20 68W25 90C27 90C59

Cite Review PDF

Full Text: DOI HAL

Zhang, Zhao; Li, Xiaoting; Shi, Yishuo; Nie, Hongmei; Zhu, Yuqing

PTAS for minimum \(k\)-path vertex cover in ball graph. (English) Zbl 1401.68365

Inf. Process. Lett. 119, 9-13 (2017).

MSC: 68W25 05C70 05C85

Cite Review PDF

Full Text: DOI

Das, Gautam K.; De, Minati; Kolay, Sudeshna; Nandy, Subhas C.; Sur-Kolay, Susmita

Approximation algorithms for maximum independent set of a unit disk graph. (English) Zbl 1317.68272

Inf. Process. Lett. 115, No. 3, 439-446 (2015).

MSC: 68W25 05C69 05C85 68Q25 68R10

Cite Review PDF

Full Text: DOI

Chan, Timothy M.; Grant, Elyot

Exact algorithms and APX-hardness results for geometric packing and covering problems. (English) Zbl 1283.52032

Comput. Geom. 47, No. 2, Part A, 112-124 (2014).

MSC: 52C45 90C39

Cite Review PDF

Full Text: DOI

Chepoi, Victor; Felsner, Stefan

Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve. (English) Zbl 1270.05028

Comput. Geom. 46, No. 9, 1036-1041 (2013).

MSC: 05B40 68W25 05D15

Cite Review PDF

Full Text: DOI Link

Chan, Timothy M.; Har-Peled, Sariel

Approximation algorithms for maximum independent set of pseudo-disks. (English) Zbl 1248.05135

Discrete Comput. Geom. 48, No. 2, 373-392 (2012).

MSC: 05C69 68W25 05C10 05B25

Cite Review PDF

Full Text: DOI

Chalermsook, Parinya

Coloring and maximum independent set of rectangles. (English) Zbl 1343.90076

Goldberg, Leslie Ann (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 14th international workshop, APPROX 2011, and 15th international workshop, RANDOM 2011, Princeton, NJ, USA, August 17–19, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22934-3/pbk). Lecture Notes in Computer Science 6845, 123-134 (2011).

MSC: 90C27 68W25

Cite Review PDF

Full Text: DOI

Bar-Yehuda, Reuven; Hermelin, Danny; Rawitz, Dror

Minimum vertex cover in rectangle graphs. (English) Zbl 1225.05199

Comput. Geom. 44, No. 6-7, 356-364 (2011).

MSC: 05C70 05C35 05C10 68W25

Cite Review PDF

Full Text: DOI

Mustafa, Nabil H.; Ray, Saurabh

Improved results on geometric hitting set problems. (English) Zbl 1207.68420

Discrete Comput. Geom. 44, No. 4, 883-895 (2010).

MSC: 68U05 52B55 52C15 68W25

Cite Review PDF

Full Text: DOI

Found 18 Documents (Results 1–18)

Independent set in \(k\)-claw-free graphs: conditional \(\chi \)-boundedness and the power of LP/SDP relaxations. (English) Zbl 07883489

Balanced independent and dominating sets on colored interval graphs. (English) Zbl 1490.68147

Robust online algorithms for dynamic choosing problems. (English) Zbl 07495154

Local search is a PTAS for feedback vertex set in minor-free graphs. (English) Zbl 1461.68157

Near-linear algorithms for geometric hitting sets and set covers. (English) Zbl 1448.68445

A simple local search gives a PTAS for the feedback vertex set problem in minor-free graphs. (English) Zbl 1534.68181

Approximation schemes for geometric coverage problems. (English) Zbl 1522.68636

PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs. (English) Zbl 1382.05037

Geometric packing under nonuniform constraints. (English) Zbl 1380.68393

Limits of local search: quality and efficiency. (English) Zbl 1369.68339

PTAS for minimum \(k\)-path vertex cover in ball graph. (English) Zbl 1401.68365

Approximation algorithms for maximum independent set of a unit disk graph. (English) Zbl 1317.68272

Exact algorithms and APX-hardness results for geometric packing and covering problems. (English) Zbl 1283.52032

Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve. (English) Zbl 1270.05028

Approximation algorithms for maximum independent set of pseudo-disks. (English) Zbl 1248.05135

Coloring and maximum independent set of rectangles. (English) Zbl 1343.90076

Minimum vertex cover in rectangle graphs. (English) Zbl 1225.05199

Improved results on geometric hitting set problems. (English) Zbl 1207.68420

Filter Results by …

Document Type

Author

Serial

Year of Publication

Main Field

Software