Polynomial kernel for interval vertex deletion. (English) Zbl 07753162
MSC:
68-XX
Found 32 Documents (Results 1–32)
On the lossy kernelization for connected treedepth deletion set. (English) Zbl 07682411
Bekos, Michael A. (ed.) et al., Graph-theoretic concepts in computer science. 48th international workshop, WG 2022, Tübingen, Germany, June 22–24, 2022. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 13453, 201-214 (2022).
MSC:
68R10
Exploiting \(c\)-closure in kernelization algorithms for graph problems. (English) Zbl 07651204
Grandoni, Fabrizio (ed.) et al., 28th annual European symposium on algorithms. ESA 2020, September 7–9, 2020, Pisa, Italy, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 173, Article 65, 17 p. (2020).
MSC:
68Wxx
Hans Bodlaender and the theory of kernelization lower bounds. (English) Zbl 07604202
Fomin, Fedor V. (ed.) et al., Treewidth, kernels, and algorithms. Essays dedicated to Hans L. Bodlaender on the occasion of his 60th birthday. Cham: Springer. Lect. Notes Comput. Sci. 12160, 18-21 (2020).
MSC:
68-XX
On the complexity of broadcast domination and Multipacking in digraphs. (English) Zbl 1518.68263
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, 264-276 (2020).
An approximate kernel for connected feedback vertex set. (English) Zbl 07525514
Bender, Michael A. (ed.) et al., 27th annual European symposium on algorithms, ESA 2019, Munich/Garching, Germany, September 9–11, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 144, Article 77, 14 p. (2019).
MSC:
68Wxx
Dual parameterization of weighted coloring. (English) Zbl 1520.68106
Paul, Christophe (ed.) et al., 13th international symposium on parameterized and exact computation, IPEC 2018, August 22–24, 2018, Helsinki, Finland. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 115, Article 12, 14 p. (2019).
Triangle packing in (sparse) tournaments: approximation and kernelization. (English) Zbl 1442.68160
Pruhs, Kirk (ed.) et al., 25th European symposium on algorithms, ESA 2017, Vienna, Austria, September 4–6, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 87, Article 14, 13 p. (2017).
Sparsification upper and lower bounds for graph problems and not-all-equal SAT. (English) Zbl 1372.68129
Lossy kernelization. (English) Zbl 1370.68136
Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 224-237 (2017).
AND-compression of NP-complete problems: streamlined proof and minor observations. (English) Zbl 1350.68118
Uniform kernelization complexity of hitting forbidden minors. (English) Zbl 1441.68107
Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part I. Berlin: Springer. Lect. Notes Comput. Sci. 9134, 629-641 (2015).
Deterministic algorithms for matching and packing problems based on representative sets. (English) Zbl 1330.68111
AND-compression of NP-complete problems: streamlined proof and minor observations. (English) Zbl 1341.68054
Cygan, Marek (ed.) et al., Parameterized and exact computation. 9th international symposium, IPEC 2014, Wroclaw, Poland, September 10–12, 2014. Revised selected papers. Cham: Springer (ISBN 978-3-319-13523-6/pbk; 978-3-319-13524-3/ebook). Lecture Notes in Computer Science 8894, 184-195 (2014).
Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem. (English) Zbl 1423.68216
Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 114-122 (2012).
Weak compositions and their applications to polynomial lower bounds for kernelization. (English) Zbl 1421.68086
Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 104-113 (2012).
Kernelization of packing problems. (English) Zbl 1421.68072
Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 68-81 (2012).
Filter Results by …
Document Type
- Journal Articles (19)
- Collection Articles (13)
all
top 5
Author
- Saurabh, Saket (6)
- Jansen, Bart M. P. (4)
- Lokshtanov, Daniel (4)
- Araújo, Júlio César Silva (3)
- Campos, Victor A. (3)
- Dell, Holger (3)
- Hermelin, Danny (3)
- Koana, Tomohiro (3)
- Komusiewicz, Christian (3)
- Kratsch, Stefan (3)
- Majumdar, Diptapriyo (3)
- Ramanujan, M. S. (3)
- Sau, Ignasi (3)
- Sommer, Frank (3)
- Zehavi, Meirav (3)
- Agrawal, Akanksha (2)
- Bougeret, Marin (2)
- Lima, Carlos Vinicius Gomes Costa (2)
- Panolan, Fahad (2)
- Silva, Ana Shirley (2)
- Wu, Xi (2)
- Bessy, Stéphane (1)
- Bliznets, Ivan A. (1)
- Bodlaender, Hans L. (1)
- Cygan, Marek (1)
- Derbisz, Jan (1)
- dos Santos, Vinícius Fernandes (1)
- Drucker, Andrew (1)
- Eiben, Eduard (1)
- Fernandes, Dos Santos Viníícius (1)
- Foucaud, Florent (1)
- Giannopoulou, Archontia C. (1)
- Goyal, Prachi (1)
- Gras, Benjamin (1)
- Kanesh, Lawqueen (1)
- Madathil, Jayakrishnan (1)
- Marx, Dániel (1)
- Misra, Neeldhara (1)
- Misra, Pranabendu (1)
- Mnich, Matthias (1)
- Mouawad, Amer E. (1)
- Perez, Anthony (1)
- Pieterse, Astrid (1)
- Pilipczuk, Marcin L. (1)
- Pilipczuk, Michał (1)
- Sagunov, Danil (1)
- Sahu, Abhishek (1)
- Sikora, Florian (1)
- Sołtys, Karolina (1)
- Thiebaut, Jocelyn (1)
- Van Leeuwen, Erik Jan (1)
- Verma, Shaily (1)
- Wahlström, Magnus (1)
- Wojtaszczyk, Jakub Onufry (1)
all
top 5
Serial
- Algorithmica (10)
- SIAM J. Discrete Math. (3)
- Theor. Comput. Sci. (2)
- Discrete Appl. Math. (1)
- SIAM J. Comput. (1)
- ACM Trans. Algorithms (1)
- Comput. Sci. Rev. (1)
