×

Found 197 Documents (Results 1–100)

On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves. (English) Zbl 07745718

Mavronicolas, Marios (ed.), Algorithms and complexity. 13th international conference, CIAC 2023, Larnaca, Cyprus, June 13–16, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13898, 353-367 (2023).
MSC:  68Wxx
PDFBibTeX XMLCite
Full Text: DOI

A survey on the complexity of flood-filling games. (English) Zbl 1514.68214

Böckenhauer, Hans-Joachim (ed.) et al., Adventures between lower bounds and higher altitudes. Essays dedicated to Juraj Hromkovič on the occasion of his 60th birthday. Cham: Springer. Lect. Notes Comput. Sci. 11011, 357-376 (2018).
PDFBibTeX XMLCite
Full Text: DOI

What is known about vertex cover kernelization? (English) Zbl 1514.68213

Böckenhauer, Hans-Joachim (ed.) et al., Adventures between lower bounds and higher altitudes. Essays dedicated to Juraj Hromkovič on the occasion of his 60th birthday. Cham: Springer. Lect. Notes Comput. Sci. 11011, 330-356 (2018).
MSC:  68R10 05C70 68Q27
PDFBibTeX XMLCite
Full Text: DOI arXiv

Surfing with Rod. (English) Zbl 1359.01039

Day, Adam (ed.) et al., Computability and complexity. Essays dedicated to Rodney G. Downey on the occasion of his 60th birthday. Cham: Springer (ISBN 978-3-319-50061-4/pbk; 978-3-319-50062-1/ebook). Lecture Notes in Computer Science 10010, 9-18 (2017).
MSC:  01A70 68-03
PDFBibTeX XMLCite
Full Text: DOI

The Flood-It game parameterized by the vertex cover number. (English) Zbl 1347.05122

Campêlo, Manoel (ed.) et al., LAGOS ’15. Selected papers of the 8th Latin-American algorithms, graphs, and optimization symposium, Praia das Fontes, Beberibe, Brazil, May 11–15, 2015. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 50, 35-40, electronic only (2015).
PDFBibTeX XMLCite
Full Text: DOI

On the parameterized complexity of dynamic problems with connectivity constraints. (English) Zbl 1434.68204

Zhang, Zhao (ed.) et al., Combinatorial optimization and applications. 8th international conference, COCOA 2014, Wailea, Maui, HI, USA, December 19–21, 2014. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 8881, 625-636 (2014).
MSC:  68Q27 05C69 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Myhill-Nerode methods for hypergraphs. (English) Zbl 1329.68129

Cai, Leizhen (ed.) et al., Algorithms and computation. 24th international symposium, ISAAC 2013, Hong Kong, China, December 16–18, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-45029-7/pbk). Lecture Notes in Computer Science 8283, 372-382 (2013).
PDFBibTeX XMLCite
Full Text: DOI arXiv

FPT is characterized by useful obstruction sets. (English) Zbl 1417.68051

Brandstädt, Andreas (ed.) et al., Graph-theoretic concepts in computer science. 39th international workshop, WG 2013, Lübeck, Germany, June 19–21, 2013. Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 8165, 261-273 (2013).
MSC:  68Q17 05C85 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

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

Parameterized approximation via fidelity preserving transformations. (English) Zbl 1272.68459

Czumaj, Artur (ed.) et al., Automata, languages, and programming. 39th international colloquium, ICALP 2012, Warwick, UK, July 9–13, 2012. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-31593-0/pbk). Lecture Notes in Computer Science 7391, 351-362 (2012).
MSC:  68W25 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average. (English) Zbl 1246.68129

Chakraborthy, Supraik (ed.) et al., IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2011), Mumbai, India, December 12–14, 2011. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-34-7). LIPIcs – Leibniz International Proceedings in Informatics 13, 229-240, electronic only (2011).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI

Parameterized complexity of the firefighter problem. (English) Zbl 1350.68128

Asano, Takao (ed.) et al., Algorithms and computation. 22nd international symposium, ISAAC 2011, Yokohama, Japan, December 5–8, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-25590-8/pbk). Lecture Notes in Computer Science 7074, 643-652 (2011).
MSC:  68Q25 05C35 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Recent developments in the theory of pre-processing. (English) Zbl 1329.68138

Atallah, Mikhail (ed.) et al., Frontiers in algorithmics and algorithmic aspects in information and management. Joint international conference, FAW-AAIM 2011, Jinhua, China, May 28–31, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-21203-1/pbk). Lecture Notes in Computer Science 6681, 4-5 (2011).
MSC:  68Q25 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Determining the winner of a Dodgson election is hard. (English) Zbl 1245.68091

Lodaya, Kamal (ed.) et al., IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2010), December 15–18, 2010, Chennai, India. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-23-1). LIPIcs – Leibniz International Proceedings in Informatics 8, 459-468, electronic only (2010).
MSC:  68Q17 68Q25 91B12
PDFBibTeX XMLCite
Full Text: DOI Link

Parameterizing by the number of numbers. (English) Zbl 1309.68092

Raman, Venkatesh (ed.) et al., Parameterized and exact computation. 5th international symposium, IPEC 2010, Chennai, India, December 13–15, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-17492-6/pbk). Lecture Notes in Computer Science 6478, 123-134 (2010).
MSC:  68Q25 68Q17 68Q45
PDFBibTeX XMLCite
Full Text: DOI arXiv

Milling a graph with turn costs: a parameterized complexity perspective. (English) Zbl 1309.68093

Thilikos, Dimitrios M. (ed.), Graph theoretic concepts in computer science. 36th international workshop, WG 2010, Zarós, Crete, Greece, June 28–30, 2010. Revised papers. Berlin: Springer (ISBN 978-3-642-16925-0/pbk). Lecture Notes in Computer Science 6410, 123-134 (2010).
MSC:  68Q25 05C12 05C85
PDFBibTeX XMLCite
Full Text: DOI

A linear kernel for co-path/cycle packing. (English) Zbl 1286.05131

Chen, Bo (ed.), Algorithmic aspects in information and management. 6th international conference, AAIM 2010, Weihai, China, July 19–21, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-14354-0/pbk). Lecture Notes in Computer Science 6124, 90-102 (2010).
MSC:  05C70 68Q17 68W25
PDFBibTeX XMLCite
Full Text: DOI

The parameterized complexity of some minimum label problems. (English) Zbl 1273.68166

Paul, Christophe (ed.) et al., Graph-theoretic concepts in computer science. 35th international workshop, WG 2009, Montpellier, France, June 24–26, 2009. Revised papers. Berlin: Springer (ISBN 978-3-642-11408-3/pbk). Lecture Notes in Computer Science 5911, 88-99 (2010).
MSC:  68Q25 05C78 05C85
PDFBibTeX XMLCite
Full Text: DOI

A generalization of Nemhauser and Trotter’s local optimization theorem. (English) Zbl 1236.68086

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, 409-420, electronic only (2009).
MSC:  68Q17 05C85 05C07
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

What makes equitable connected partition easy. (English) Zbl 1273.68164

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, 122-133 (2009).
MSC:  68Q25 05C70 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Towards fully multivariate algorithmics: some new results and directions in parameter ecology. (English) Zbl 1267.68302

Fiala, Jiří (ed.) et al., Combinatorial algorithms. 20th international workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28–July 2, 2009. Revised selected papers. Berlin: Springer (ISBN 978-3-642-10216-5/pbk). Lecture Notes in Computer Science 5874, 2-10 (2009).
MSC:  68W01 05C85 68Q25
PDFBibTeX XMLCite
Full Text: DOI

A complexity dichotomy for finding disjoint solutions of vertex deletion problems. (English) Zbl 1250.68125

Královič, Rastislav (ed.) et al., Mathematical foundations of computer science 2009. 34th international symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24–28, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03815-0/pbk). Lecture Notes in Computer Science 5734, 319-330 (2009).
MSC:  68Q25 68Q17 68R10
PDFBibTeX XMLCite
Full Text: DOI

Graph-based data clustering with overlaps. (English) Zbl 1248.68377

Ngo, Hung Q. (ed.), Computing and combinatorics. 15th annual international conference, COCOON 2009, Niagara Falls, NY, USA, July 13–15, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02881-6/pbk). Lecture Notes in Computer Science 5609, 516-526 (2009).
MSC:  68R10 05C69 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Distortion is fixed parameter tractable. (English) Zbl 1248.68244

Albers, Susanne (ed.) et al., Automata, languages and programming. 36th international colloquium, ICALP 2009, Rhodes, Greece, July 5–12, 2009. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-02926-4/pbk). Lecture Notes in Computer Science 5555, 463-474 (2009).
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

Parameterized complexity of stabbing rectangles and squares in the plane. (English) Zbl 1211.68465

Das, Sandip (ed.) et al., WALCOM: Algorithms and computation. Third international workshop, WALCOM 2009, Kolkata, India, February 18–20, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-00201-4/pbk). Lecture Notes in Computer Science 5431, 298-309 (2009).
MSC:  68U05 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Clustering with partial information. (English) Zbl 1173.68596

Ochmański, Edward (ed.) et al., Mathematical foundations of computer science 2008. 33rd international symposium, MFCS 2008, Toruń Poland, August 25–29, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85237-7/pbk). Lecture Notes in Computer Science 5162, 144-155 (2008).
PDFBibTeX XMLCite
Full Text: DOI

Leaf powers and their properties: Using the trees. (English) Zbl 1183.68425

Hong, Seok-Hee (ed.) et al., Algorithms and computation. 19th international symposium, ISAAC 2008, Gold Coast, Australia, December 15–17, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-92181-3/pbk). Lecture Notes in Computer Science 5369, 402-413 (2008).
MSC:  68R10 68Q45
PDFBibTeX XMLCite
Full Text: DOI

Graph layout problems parameterized by vertex cover. (English) Zbl 1183.68424

Hong, Seok-Hee (ed.) et al., Algorithms and computation. 19th international symposium, ISAAC 2008, Gold Coast, Australia, December 15–17, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-92181-3/pbk). Lecture Notes in Computer Science 5369, 294-305 (2008).
MSC:  68R10 68Q25 90C35
PDFBibTeX XMLCite
Full Text: DOI Link

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

Facility location problems: A parameterized view. (English) Zbl 1143.90354

Fleischer, Rudolf (ed.) et al., Algorithmic aspects in information and management. 4th international conference, AAIM 2008, Shanghai, China, June 23–25, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-68865-5/pbk). Lecture Notes in Computer Science 5034, 188-199 (2008).
MSC:  90B80
PDFBibTeX XMLCite
Full Text: DOI

Fixed-parameter algorithms for Kemeny scores. (English) Zbl 1143.91319

Fleischer, Rudolf (ed.) et al., Algorithmic aspects in information and management. 4th international conference, AAIM 2008, Shanghai, China, June 23–25, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-68865-5/pbk). Lecture Notes in Computer Science 5034, 60-71 (2008).
MSC:  91B12 68W05
PDFBibTeX XMLCite
Full Text: DOI

Parameterized algorithms and hardness results for some graph motif problems. (English) Zbl 1143.68501

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, 31-43 (2008).
PDFBibTeX XMLCite
Full Text: DOI Link

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

Quadratic kernelization for convex recoloring of trees. (English) Zbl 1206.68141

Lin, Guohui (ed.), Computing and combinatorics. 13th annual international conference, COCOON 2007, Banff, Canada, July 16–19, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73544-1/pbk). Lecture Notes in Computer Science 4598, 86-96 (2007).
PDFBibTeX XMLCite
Full Text: DOI

Connected coloring completion for general graphs: algorithms and complexity. (English) Zbl 1206.05040

Lin, Guohui (ed.), Computing and combinatorics. 13th annual international conference, COCOON 2007, Banff, Canada, July 16–19, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73544-1/pbk). Lecture Notes in Computer Science 4598, 75-85 (2007).
PDFBibTeX XMLCite
Full Text: DOI

On the complexity of some colorful problems parameterized by treewidth. (English) Zbl 1175.68292

Dress, Andreas (ed.) et al., Combinatorial optimization and applications. First international conference, COCOA 2007, Xi’an, China, August 14–16, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73555-7/pbk). Lecture Notes in Computer Science 4616, 366-377 (2007).
PDFBibTeX XMLCite
Full Text: DOI Link

Efficient parameterized preprocessing for cluster editing. (English) Zbl 1135.68511

Csuhaj-Varjú, Erzsébet (ed.) et al., Fundamentals of computation theory. 16th international symposium, FCT 2007, Budapest, Hungary, August 27–30, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-74239-5/pbk). Lecture Notes in Computer Science 4639, 312-321 (2007).
MSC:  68R10
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

The complexity ecology of parameters: an illustration using bounded max leaf number. (English) Zbl 1151.68426

Cooper, S. Barry (ed.) et al., Computation and logic in the real world. Third conference on computability in Europe, CiE 2007, Siena, Italy, June 18–23, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73000-2/pbk). Lecture Notes in Computer Science 4497, 268-277 (2007).
MSC:  68Q25 05C85
PDFBibTeX XMLCite
Full Text: DOI

Clique-width minimization is NP-hard. (English) Zbl 1301.68145

Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 354-362 (2006).
MSC:  68Q17 05C69
PDFBibTeX XMLCite
Full Text: DOI

The lost continent of polynomial time: Preprocessing and kernelization. (English) Zbl 1154.68560

Bodlaender, Hans L. (ed.) et al., Parameterized and exact computation. Second international workshop, IWPEC 2006, Zürich, Switzerland, September 13–15, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-39098-5/pbk). Lecture Notes in Computer Science 4169, 276-277 (2006).
MSC:  68W01 68-03 68Q25
PDFBibTeX XMLCite
Full Text: DOI

The undirected feedback vertex set problem has a Poly\((k)\) kernel. (English) Zbl 1154.68421

Bodlaender, Hans L. (ed.) et al., Parameterized and exact computation. Second international workshop, IWPEC 2006, Zürich, Switzerland, September 13–15, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-39098-5/pbk). Lecture Notes in Computer Science 4169, 192-202 (2006).
MSC:  68Q25 68R10
PDFBibTeX XMLCite
Full Text: DOI

Parameterized approximation problems. (English) Zbl 1154.68572

Bodlaender, Hans L. (ed.) et al., Parameterized and exact computation. Second international workshop, IWPEC 2006, Zürich, Switzerland, September 13–15, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-39098-5/pbk). Lecture Notes in Computer Science 4169, 121-129 (2006).
MSC:  68W25 68Q25
PDFBibTeX XMLCite
Full Text: DOI

nonblocker: Parameterized algorithmics for minimum dominating set. (English) Zbl 1175.68543

Wiedermann, Jiří (ed.) et al., SOFSEM 2006: Theory and practice of computer science. 32nd conference on current trends in theory and practice of computer science, Měřín, Czech Republic, January 21–27, 2006. Proceedings. Berlin: Springer (ISBN 3-540-31198-X/pbk). Lecture Notes in Computer Science 3831, 237-245 (2006).
MSC:  68W05 05C69 68W40
PDFBibTeX XMLCite
Full Text: DOI

An \(O (2^{ O (k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem. (English) Zbl 1128.68400

Wang, Lusheng (ed.), Computing and combinatorics. 11th annual international conference, COCOON 2005, Kunming, China, August 16–29, 2005. Proceedings. Berlin: Springer (ISBN 3-540-28061-8/pbk). Lecture Notes in Computer Science 3595, 859-869 (2005).
MSC:  68R10 05C85 68Q25
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

Biographic Reference