×

Found 57 Documents (Results 1–57)

Hardness and approximation results for some variants of stable marriage problem. (English) Zbl 07683177

Balachandran, Niranjan (ed.) et al., Algorithms and discrete applied mathematics. 8th international conference, CALDAM 2022, Puducherry, India, February 10–12, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13179, 252-264 (2022).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem. (English) Zbl 07603885

Koenemann, Jochen (ed.) et al., Approximation and online algorithms. 19th international workshop, WAOA 2021, Lisbon, Portugal, September 6–10, 2021. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 12982, 65-79 (2021).
MSC:  68W25 68W27
PDFBibTeX XMLCite
Full Text: DOI

Improved budgeted connected domination and budgeted edge-vertex domination. (English) Zbl 07601021

Gąsieniec, Leszek (ed.) et al., Combinatorial algorithms. 31st international workshop, IWOCA 2020, Bordeaux, France, June 8–10, 2020, Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12126, 368-381 (2020).
MSC:  68Rxx 68Wxx
PDFBibTeX XMLCite
Full Text: DOI

Approximation algorithms for facial cycles in planar embeddings. (English) Zbl 07561395

Hsu, Wen-Lian (ed.) et al., 29th international symposium on algorithms and computation, ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 123, Article 41, 13 p. (2018).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

New results on directed edge dominating set. (English) Zbl 1512.68191

Potapov, Igor (ed.) et al., 43rd international symposium on mathematical foundations of computer science. MFCS 2018, Liverpool, United Kingdom, August 27–31, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 117, Article 67, 16 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Approximating dominating set on intersection graphs of rectangles and L-frames. (English) Zbl 1512.68400

Potapov, Igor (ed.) et al., 43rd international symposium on mathematical foundations of computer science. MFCS 2018, Liverpool, United Kingdom, August 27–31, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 117, Article 37, 15 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Fast and simple local algorithms for 2-edge dominating sets and 3-total vertex covers. (English) Zbl 1475.68242

Kaykobad, Mohammad (ed.) et al., WALCOM: algorithms and computation. 10th international workshop, WALCOM 2016, Kathmandu, Nepal, March 29–31, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9627, 251-262 (2016).
PDFBibTeX XMLCite
Full Text: DOI

A \((2 - c \frac{\log {n}}{n})\) approximation algorithm for the minimum maximal matching problem. (English) Zbl 1209.68640

Bampis, Evripidis (ed.) et al., Approximation and online algorithms. 6th international workshop, WAOA 2008, Karlsruhe, Germany, September 18–19, 2008. Revised papers. Berlin: Springer (ISBN 978-3-540-93979-5/pbk). Lecture Notes in Computer Science 5426, 267-278 (2009).
MSC:  68W25 05C70 05C85
PDFBibTeX XMLCite
Full Text: DOI

Minimum maximal matching is NP-hard in regular bipartite graphs. (English) Zbl 1139.05337

Agrawal, Manindra (ed.) et al., Theory and applications of models of computation. 5th international conference, TAMC 2008, Xi’an, China, April 25–29, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79227-7/pbk). Lecture Notes in Computer Science 4978, 364-374 (2008).
MSC:  05C70 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

Software