×

Found 93 Documents (Results 1–93)

Efficient fully dynamic elimination forests with applications to detecting long paths and cycles. (English) Zbl 07788388

Marx, Dániel (ed.), Proceedings of the 32nd annual ACM-SIAM symposium on discrete algorithms, SODA 2021, Alexandria, VA, USA, virtual, January 10–13, 2021. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 796-809 (2021).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

On computing centroids according to the \(p\)-norms of Hamming distance vectors. (English) Zbl 07525465

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 28, 16 p. (2019).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

SETH-based lower bounds for subset sum and bicriteria path. (English) Zbl 1431.68040

Chan, Timothy M. (ed.), Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019, San Diego, CA, USA, January 6–9, 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 41-57 (2019).
MSC:  68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

How hard is it to satisfy (almost) all roommates? (English) Zbl 1499.68131

Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 35, 15 p. (2018).
MSC:  68Q17 68Q27 91B68
PDFBibTeX XMLCite
Full Text: DOI arXiv

The clever shopper problem. (English) Zbl 1434.68193

Fomin, Fedor V. (ed.) et al., Computer science – theory and applications. 13th international computer science symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10846, 53-64 (2018).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Diminishable parameterized problems and strict polynomial kernelization. (English) Zbl 1485.68116

Manea, Florin (ed.) et al., Sailing routes in the world of computation. 14th conference on computability in Europe, CiE 2018, Kiel, Germany, July 30 – August 3, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10936, 161-171 (2018).
MSC:  68Q27 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

Lossy kernels for hitting subgraphs. (English) Zbl 1441.68175

Larsen, Kim G. (ed.) et al., 42nd international symposium on mathematical foundations of computer science, MFCS 2017, August 21–25, 2017, Aalborg, Denmark. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 83, Article 67, 14 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI

11th international symposium on parameterized and exact computation (IPEC 2016), Aarhus, Denmark, August 24–26, 2016. Proceedings. (English) Zbl 1360.68013

LIPIcs – Leibniz International Proceedings in Informatics 63. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-023-1). xiv, 30 articles, not consecutively paged, electronic only, open access (2017).
PDFBibTeX XMLCite
Full Text: Link

A biclique approach to reference anchored gene blocks and its applications to pathogenicity islands. (English) Zbl 1383.92024

Frith, Martin (ed.) et al., Algorithms in bioinformatics. 16th international workshop, WABI 2016, Aarhus, Denmark, August 22–24, 2016. Proceedings. Cham: Springer (ISBN 978-3-319-43680-7/pbk; 978-3-319-43681-4/ebook). Lecture Notes in Computer Science 9838. Lecture Notes in Bioinformatics, 14-26 (2016).
PDFBibTeX XMLCite
Full Text: DOI

Fractals for kernelization lower bounds, with an application to length-bounded cut problems. (English) Zbl 1388.68111

Chatzigiannakis, Ioannis (ed.) et al., 43rd international colloquium on automata, languages, and programming, ICALP 2016, Rome, Italy, July 12–15, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-013-2). LIPIcs – Leibniz International Proceedings in Informatics 55, Article 25, 14 p. (2016).
MSC:  68Q25 68Q17 68R10
PDFBibTeX XMLCite
Full Text: DOI

Parameterized complexity of critical node cuts. (English) Zbl 1378.68081

Husfeldt, Thore (ed.) et al., 10th international symposium on parameterized and exact computation, IPEC 2015, Patras, Greece, September 16–18, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-92-7). LIPIcs – Leibniz International Proceedings in Informatics 43, 343-354 (2015).
MSC:  68Q25 68Q17 68R10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Scheduling two competing agents when one agent has significantly fewer jobs. (English) Zbl 1378.68021

Husfeldt, Thore (ed.) et al., 10th international symposium on parameterized and exact computation, IPEC 2015, Patras, Greece, September 16–18, 2015. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-92-7). LIPIcs – Leibniz International Proceedings in Informatics 43, 55-65 (2015).
MSC:  68M20 68Q17 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Parameterized complexity dichotomy for Steiner Multicut. (English) Zbl 1355.68113

Mayr, Ernst W. (ed.) et al., 32nd international symposium on theoretical aspects of computer science, STACS’15, Garching, Germany, March 4–7, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-78-1). LIPIcs – Leibniz International Proceedings in Informatics 30, 157-170 (2015).
PDFBibTeX XMLCite
Full Text: DOI

Parameterized complexity analysis for the closest string with wildcards problem. (English) Zbl 1407.68225

Kulikov, Alexander S. (ed.) et al., Combinatorial pattern matching. 25th annual symposium, CPM 2014, Moscow, Russia, June 16–18, 2014. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8486, 140-149 (2014).
MSC:  68Q25 68W32
PDFBibTeX XMLCite
Full Text: DOI

A completeness theory for polynomial (Turing) kernelization. (English) Zbl 1407.68224

Gutin, Gregory (ed.) et al., Parameterized and exact computation. 8th international symposium, IPEC 2013, Sophia Antipolis, France, September 4–6, 2013. Revised selected papers. Berlin: Springer. Lect. Notes Comput. Sci. 8246, 202-215 (2013).
MSC:  68Q25 68Q15 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Binary jumbled pattern matching on trees and tree-like structures. (English) Zbl 1323.68634

Bodlaender, Hans L. (ed.) et al., Algorithms – ESA 2013. 21st annual European symposium, Sophia Antipolis, France, September 2–4, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-40449-8/pbk). Lecture Notes in Computer Science 8125, 517-528 (2013).
MSC:  68W32
PDFBibTeX XMLCite
Full Text: DOI

Tractable parameterizations for the minimum linear arrangement problem. (English) Zbl 1394.68441

Bodlaender, Hans L. (ed.) et al., Algorithms – ESA 2013. 21st annual European symposium, Sophia Antipolis, France, September 2–4, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-40449-8/pbk). Lecture Notes in Computer Science 8125, 457-468 (2013).
PDFBibTeX XMLCite
Full Text: DOI

Tight kernel bounds for problems on graphs with small degeneracy (extended abstract). (English) Zbl 1394.68173

Bodlaender, Hans L. (ed.) et al., Algorithms – ESA 2013. 21st annual European symposium, Sophia Antipolis, France, September 2–4, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-40449-8/pbk). Lecture Notes in Computer Science 8125, 361-372 (2013).
MSC:  68Q27 68R10
PDFBibTeX XMLCite
Full Text: DOI

Local search for string problems: brute force is essentially optimal. (English) Zbl 1381.68314

Fischer, Johannes (ed.) et al., Combinatorial pattern matching. 24th annual symposium, CPM 2013, Bad Herrenalb, Germany, June 17–19, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38904-7/pbk). Lecture Notes in Computer Science 7922, 130-141 (2013).
MSC:  68W32 68P10
PDFBibTeX XMLCite
Full Text: DOI

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).
MSC:  68Q25 68Q17 68R10
PDFBibTeX XMLCite
Full Text: Link

Algorithmic aspects of the intersection and overlap numbers of a graph. (English) Zbl 1260.68177

Chao, Kun-Mao (ed.) et al., Algorithms and computation. 23rd international symposium, ISAAC 2012, Taipei, Taiwan, December 19–21, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-35260-7/pbk). Lecture Notes in Computer Science 7676, 465-474 (2012).
MSC:  68Q25 05C35 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Optimization problems in dotted interval graphs. (English) Zbl 1341.05190

Golumbic, Martin Charles (ed.) et al., Graph-theoretic concepts in computer science. 38th international workshop, WG 2012, Jerusalem, Israel, June 26–28, 2012. Revised selected papers. Berlin: Springer (ISBN 978-3-642-34610-1/pbk). Lecture Notes in Computer Science 7551, 46-56 (2012).
MSC:  05C69 05C70
PDFBibTeX XMLCite
Full Text: DOI

Parameterized complexity of induced \(H\)-matching on claw-free graphs. (English) Zbl 1365.68282

Epstein, Leah (ed.) et al., Algorithms – ESA 2012. 20th annual European symposium, Ljubljana, Slovenia, September 10–12, 2012. Proceeding. Berlin: Springer (ISBN 978-3-642-33089-6/pbk). Lecture Notes in Computer Science 7501, 624-635 (2012).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Parameterized two-player Nash equilibrium. (English) Zbl 1341.05160

Kolman, Petr (ed.) et al., Graph-theoretic concepts in computer science. 37th international workshop, WG 2011, Teplá Monastery, Czech Republic, June 21–24, 2011. Revised papers. Berlin: Springer (ISBN 978-3-642-25869-5/pbk). Lecture Notes in Computer Science 6986, 215-226 (2011).
MSC:  05C57 91A43 91A05
PDFBibTeX XMLCite
Full Text: DOI arXiv

Distance oracles for vertex-labeled graphs. (English) Zbl 1333.68212

Aceto, Luca (ed.) et al., Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4–8, 2011. Proceedings, Part II. Berlin: Springer (ISBN 978-3-642-22011-1/pbk). Lecture Notes in Computer Science 6756, 490-501 (2011).
MSC:  68R10 05C78 68P05
PDFBibTeX XMLCite
Full Text: DOI

Domination when the stars are out. (English) Zbl 1334.68160

Aceto, Luca (ed.) et al., Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4–8, 2011. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-22005-0/pbk). Lecture Notes in Computer Science 6755, 462-473 (2011).
PDFBibTeX XMLCite
Full Text: DOI arXiv

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

de Berg, Mark (ed.) et al., Algorithms – ESA 2010. 18th annual European symposium, Liverpool, UK, September 6–8, 2010. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-15774-5/pbk). Lecture Notes in Computer Science 6346, 255-266 (2010).
MSC:  05C85 05C70 68W25
PDFBibTeX XMLCite
Full Text: DOI Link

Mod/Resc parsimony inference. (English) Zbl 1286.92016

Amir, Amihood (ed.) et al., Combinatorial pattern matching. 21st annual symposium, CPM 2010, New York, NY, USA, June 21–23, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-13508-8/pbk). Lecture Notes in Computer Science 6129, 202-213 (2010).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Optimization problems in multiple subtree graphs. (English) Zbl 1284.68669

Bampis, Evripidis (ed.) et al., Approximation and online algorithms. 7th international workshop, WAOA 2009, Copenhagen, Denmark, September 10–11, 2009. Revised papers. Berlin: Springer (ISBN 978-3-642-12449-5/pbk). Lecture Notes in Computer Science 5893, 194-204 (2010).
PDFBibTeX XMLCite
Full Text: DOI

Extension of the Nemhauser and Trotter theorem to generalized vertex cover with applications. (English) Zbl 1284.68653

Bampis, Evripidis (ed.) et al., Approximation and online algorithms. 7th international workshop, WAOA 2009, Copenhagen, Denmark, September 10–11, 2009. Revised papers. Berlin: Springer (ISBN 978-3-642-12449-5/pbk). Lecture Notes in Computer Science 5893, 13-24 (2010).
MSC:  68W25 05C85 68R10
PDFBibTeX XMLCite
Full Text: DOI

A unified algorithm for accelerating edit-distance computation via text-compression. (English) Zbl 1236.68308

Albers, Susanne (ed.) et al., STACS 2009. 26th international symposium on theoretical aspects of computer science, Freiburg, Germany, February 26–28, 2009. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-09-5). LIPIcs – Leibniz International Proceedings in Informatics 3, 529-540, electronic only (2009).
MSC:  68W32 90C39 68P30
PDFBibTeX XMLCite
Full Text: DOI Link

Well-quasi-orders in subclasses of bounded treewidth graphs. (English) Zbl 1264.68120

Chen, Jianer (ed.) et al., Parameterized and exact computation. 4th international workshop, IWPEC 2009, Copenhagen, Denmark, September 10–11, 2009. Revised selected papers. Berlin: Springer (ISBN 978-3-642-11268-3/pbk). Lecture Notes in Computer Science 5917, 149-160 (2009).
MSC:  68R10 05C85 06A99
PDFBibTeX XMLCite
Full Text: DOI

Haplotype inference constrained by plausible haplotype data. (English) Zbl 1247.92017

Kucherov, Gregory (ed.) et al., Combinatorial pattern matching. 20th annual symposium, CPM 2009, Lille, France, June 22–24, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02440-5/pbk). Lecture Notes in Computer Science 5577, 339-352 (2009).
PDFBibTeX XMLCite
Full Text: DOI

On problems without polynomial kernels (extended abstract). (English) Zbl 1153.68554

Aceto, Luca (ed.) et al., Automata, languages and programming. 35th international colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008. Proceedings, Part I. Berlin: Springer (ISBN 978-3-540-70574-1/pbk). Lecture Notes in Computer Science 5125, 563-574 (2008).
MSC:  68W05 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Constrained LCS: Hardness and approximation. (English) Zbl 1143.68637

Ferragina, Paolo (ed.) et al., Combinatorial pattern matching. 19th annual symposium, CPM 2008, Pisa, Italy, June 18–20, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-69066-5/pbk). Lecture Notes in Computer Science 5029, 255-262 (2008).
MSC:  68W25 68Q25
PDFBibTeX XMLCite
Full Text: DOI

A purely democratic characterization of W[1]. (English) Zbl 1142.68359

Grohe, Martin (ed.) et al., Parameterized and exact computation. Third international workshop, IWPEC 2008, Victoria, Canada, May 14–16, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79722-7/pbk). Lecture Notes in Computer Science 5018, 103-114 (2008).
MSC:  68Q15 94C10
PDFBibTeX XMLCite
Full Text: DOI

The minimum substring cover problem. (English) Zbl 1130.68100

Kaklamanis, Christos (ed.) et al., Approximation and online algorithms. 5th international workshop, WAOA 2007, Eilat, Israel, October 11-12, 2007. Revised papers. Berlin: Springer (ISBN 978-3-540-77917-9/pbk). Lecture Notes in Computer Science 4927, 170-183 (2008).
MSC:  68W25 68Q45 92D20
PDFBibTeX XMLCite
Full Text: DOI

Optimization problems in multiple-interval graphs. (English) Zbl 1302.05179

Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2007, New Orleans, LA, USA, January 7–9, 2007. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-0-89871-624-5). 268-277 (2007).
PDFBibTeX XMLCite

Common structured patterns in linear graphs: Approximation and combinatorics. (English) Zbl 1138.68476

Ma, Bin (ed.) et al., Combinatorial pattern matching. 18th annual symposium, CPM 2007, London, Canada, July 9–11, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73436-9/pbk). Lecture Notes in Computer Science 4580, 241-252 (2007).
MSC:  68R10 92-08 92C40
PDFBibTeX XMLCite
Full Text: DOI

Sharp tractability borderlines for finding connected motifs in vertex-colored graphs. (English) Zbl 1171.68497

Arge, Lars (ed.) et al., Automata, languages and programming. 34th international colloquium, ICALP 2007, Wrocław, Poland, July 9–13, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73419-2/pbk). Lecture Notes in Computer Science 4596, 340-351 (2007).
MSC:  68Q25 05C15 92D20
PDFBibTeX XMLCite
Full Text: DOI

Local alignment of RNA sequences with arbitrary scoring schemes. (English) Zbl 1196.68341

Lewenstein, Moshe (ed.) et al., Combinatorial pattern matching. 17th annual symposium, CPM 2006, Barcelona, Spain, July 5–7, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-35455-0/pbk). Lecture Notes in Computer Science 4009, 246-257 (2006).
MSC:  68W32 92-08 92D20
PDFBibTeX XMLCite
Full Text: DOI

Fixed-parameter algorithms for protein similarity search under mRNA structure constraints. (English) Zbl 1171.92316

Kratsch, Dieter (ed.), Graph-theoretic concepts in computer science. 31st international workshop, WG 2005, Metz, France, June 23–25, 2005. Revised selected papers. Berlin: Springer (ISBN 3-540-31000-2/pbk). Lecture Notes in Computer Science 3787, 271-282 (2005).
MSC:  92C40 68Q25 92-08
PDFBibTeX XMLCite
Full Text: DOI

Approximating the 2-interval pattern problem. (English) Zbl 1123.68143

Brodal, Gerth Stølting (ed.) et al., Algorithms – ESA 2005. 13th annual European symposium, Palma de Mallorca, Spain, October 3–6, 2005. Proceedings. Berlin: Springer (ISBN 3-540-29118-0/pbk). Lecture Notes in Computer Science 3669, 426-437 (2005).
MSC:  68W25 92D20
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

Database

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software