×

Found 63 Documents (Results 1–63)

The parameterized complexity of local search for TSP, more refined. (English) Zbl 1350.68141

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, 614-623 (2011).
MSC:  68Q25 68Q17 90C27
PDFBibTeX XMLCite
Full Text: DOI

Extended islands of tractability for parsimony haplotyping. (English) Zbl 1286.92036

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, 214-226 (2010).
MSC:  92D10 68Q25 92-08
PDFBibTeX XMLCite
Full Text: DOI

Average parameterization and partial kernelization for computing medians. (English) Zbl 1283.68391

López-Ortiz, Alejandro (ed.), LATIN 2010: Theoretical informatics. 9th Latin American symposium, Oaxaca, Mexico, April 19–23, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-12199-9/pbk). Lecture Notes in Computer Science 6034, 60-71 (2010).
MSC:  68W05 68Q25 68R01
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

Parameterized complexity of arc-weighted directed Steiner problems. (English) Zbl 1273.68174

Dong, Yingfei (ed.) et al., Algorithms and computation. 20th international symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16–18, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-10630-9/pbk). Lecture Notes in Computer Science 5878, 544-553 (2009).
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

Iterative compression for exactly solving NP-hard minimization problems. (English) Zbl 1248.68380

Lerner, Jürgen (ed.) et al., Algorithmics of large and complex networks. Design, analysis, and simulation. Berlin: Springer (ISBN 978-3-642-02093-3/pbk). Lecture Notes in Computer Science 5515, 65-80 (2009).
PDFBibTeX XMLCite
Full Text: DOI

A more relaxed model for graph-based data clustering: \(s\)-Plex Editing. (English) Zbl 1246.68171

Goldberg, Andrew V. (ed.) et al., Algorithmic aspects in information and management. 5th international conference, AAIM 2009, San Francisco, CA, USA, June 15–17, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02157-2/pbk). Lecture Notes in Computer Science 5564, 226-239 (2009).
MSC:  68R10 05C85 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Parameterized computational complexity of Dodgson and Young elections. (English) Zbl 1155.91340

Gudmundsson, Joachim (ed.), Algorithm theory – SWAT 2008. 11th Scandinavian workshop on algorithm theory, Gothenburg, Sweden, July 2–4, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-69900-2/pbk). Lecture Notes in Computer Science 5124, 402-413 (2008).
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

Probe matrix problems: Totally balanced matrices. (English) Zbl 1137.68472

Kao, Ming-Yang (ed.) et al., Algorithmic aspects in information and management. Third international conference, AAIM 2007, Portland, OR, USA, June 6–8, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-72868-9/pbk). Lecture Notes in Computer Science 4508, 368-377 (2007).
MSC:  68R10 05B20 05C50
PDFBibTeX XMLCite
Full Text: DOI

Linear problem kernels for NP-hard problems on planar graphs. (English) Zbl 1171.68488

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, 375-386 (2007).
MSC:  68Q17 68Q25 68R10
PDFBibTeX XMLCite
Full Text: DOI

Approximability and parameterized complexity of consecutive ones submatrix problems. (English) Zbl 1200.68282

Cai, Jin-Yi (ed.) et al., Theory and applications of models of computation. 4th international conference, TAMC 2007, Shanghai, China, May 22–25, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-72503-9/pbk). Lecture Notes in Computer Science 4484, 680-691 (2007).
MSC:  68W25 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Data reduction, exact, and heuristic algorithms for clique cover. (English) Zbl 1428.68216

Raman, Rajeev (ed.) et al., Proceedings of the eighth workshop on algorithm engineering and experiments (ALENEX ’06), Miami, FL, USA, January 21, 2006. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 86-94 (2006).
PDFBibTeX XMLCite
Full Text: DOI

Fixed-parameter tractability results for Full-Degree Spanning Tree and its dual. (English) Zbl 1154.68425

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, 203-214 (2006).
PDFBibTeX XMLCite
Full Text: DOI

Minimum membership set covering and the consecutive ones property. (English) Zbl 1142.68454

Arge, Lars (ed.) et al., Algorithm theory – SWAT 2006. 10th Scandinavian workshop on algorithm theory, Riga, Latvia, July 6–8, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-35753-7/pbk). Lecture Notes in Computer Science 4059, 339-350 (2006).
MSC:  68R10 05C70 90C35
PDFBibTeX XMLCite
Full Text: DOI

Fixed-parameter tractability results for feedback set problems in tournaments. (English) Zbl 1183.68419

Calamoneri, Tiziana (ed.) et al., Algorithms and complexity. 6th Italian conference, CIAC 2006, Rome, Italy, May 29–31, 2006. Proceedings. Berlin: Springer (ISBN 3-540-34375-X/pbk). Lecture Notes in Computer Science 3998, 320-331 (2006).
MSC:  68R10 05C20 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Complexity and exact algorithms for Multicut. (English) Zbl 1175.68294

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, 303-312 (2006).
MSC:  68R10 05C85 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Extending the tractability border for closest leaf powers. (English) Zbl 1171.68496

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, 397-408 (2005).
MSC:  68Q25 05C85
PDFBibTeX XMLCite
Full Text: DOI

Improved fixed-parameter algorithms for two feedback set problems. (English) Zbl 1161.68491

Dehne, Frank (ed.) et al., Algorithms and data structures. 9th international workshop, WADS 2005, Waterloo, Canada, August 15–17, 2005. Proceedings. Berlin: Springer (ISBN 3-540-28101-0/pbk). Lecture Notes in Computer Science 3608, 158-168 (2005).
PDFBibTeX XMLCite
Full Text: DOI

Parameterized complexity of generalized vertex cover problems. (English) Zbl 1161.68669

Dehne, Frank (ed.) et al., Algorithms and data structures. 9th international workshop, WADS 2005, Waterloo, Canada, August 15–17, 2005. Proceedings. Berlin: Springer (ISBN 3-540-28101-0/pbk). Lecture Notes in Computer Science 3608, 36-48 (2005).
MSC:  68R10 05C70 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Improved algorithms and complexity results for power domination in graphs. (English) Zbl 1122.68481

Liśkiewicz, Maciej (ed.) et al., Fundamentals of computation theory. 15th international symposium, FCT 2005, Lübeck, Germany, August 17–20, 2005. Proceedings. Berlin: Springer (ISBN 3-540-28193-2/pbk). Lecture Notes in Computer Science 3623, 172-184 (2005).
MSC:  68R10 05C85 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Bounded degree closest \(k\)-tree power is NP-complete. (English) Zbl 1128.68363

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, 757-766 (2005).
MSC:  68Q17 05C38 68R10
PDFBibTeX XMLCite
Full Text: DOI

Avoiding forbidden submatrices by row deletions. (English) Zbl 1202.68212

Van Emde Boas, Peter (ed.) et al., SOFSEM 2004: Theory and practice of computer science. 30th conference on current trends in theory and practice of computer science, Měřín, Czech Republik, January 24–30, 2004. Proceedings. Berlin: Springer (ISBN 3-540-20779-1/pbk). Lect. Notes Comput. Sci. 2932, 349-360 (2004).
PDFBibTeX XMLCite
Full Text: DOI

Error compensation in leaf root problems. (English) Zbl 1116.68551

Fleischer, Rudolf (ed.) et al., Algorithms and computation. 15th international symposium, ISAAC 2004, Hong Kong, China, December 20–22, 2004. Proceedings. Berlin: Springer (ISBN 3-540-24131-0/pbk). Lecture Notes in Computer Science 3341, 389-401 (2004).
MSC:  68R10 68Q17 68Q25
PDFBibTeX XMLCite
Full Text: DOI

A structural view on parameterizing problems: Distance from triviality. (English) Zbl 1104.68050

Downey, Rod (ed.) et al., Parametrized and exact computation. First international workshop, IWPEC 2004, Bergen, Norway, September 14–17, 2004. Proceedings. Berlin: Springer (ISBN 3-540-23071-8/pbk). Lecture Notes in Computer Science 3162, 162-173 (2004).
MSC:  68Q17 68Q25 68W01
PDFBibTeX XMLCite
Full Text: DOI

On exact and approximation algorithms for distinguishing substring selection. (English) Zbl 1278.68351

Lingas, Andrzej (ed.) et al., Fundamentals of computation theory. 14th international symposium, FCT 2003, Malmö, Sweden, August 12–15, 2003. Proceedings. Berlin: Springer (ISBN 3-540-40543-7/pbk). Lect. Notes Comput. Sci. 2751, 195-209 (2003).
PDFBibTeX XMLCite
Full Text: DOI

Automated generation of search tree algorithms for graph modification problems. (English) Zbl 1266.68200

Di Battista, Giuseppe (ed.) et al., Algorithms – ESA 2003. 11th annual European symposium, Budapest, Hungary, September 16–19, 2003. Proceedings. Berlin: Springer (ISBN 3-540-20064-9/pbk). Lect. Notes Comput. Sci. 2832, 642-653 (2003).
PDFBibTeX XMLCite
Full Text: DOI

Graph-modeled data clustering: Fixed-parameter algorithms for clique generation. (English) Zbl 1032.68158

Petreschi, Rosella (ed.) et al., Algorithms and complexity. 5th Italian conference, CIAC 2003, Rome, Italy, May 28-30, 2003. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2653, 108-119 (2003).
MSC:  68W05 68R10 68Q17
PDFBibTeX XMLCite
Full Text: Link

Towards optimally solving the LONGEST COMMON SUBSEQUENCE problem for sequences with nested arc annotations in linear time. (English) Zbl 1077.68738

Apostolico, Alberto (ed.) et al., Combinatorial pattern matching. 13th annual symposium, CPM 2002, Fukuoka, Japan, July 3–5, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43862-9). Lect. Notes Comput. Sci. 2373, 99-114 (2002).
PDFBibTeX XMLCite
Full Text: Link

Pattern matching for arc-annotated sequences. (English) Zbl 1027.68653

Agrawal, Manindra (ed.) et al., FST TCS 2002: Foundations of software technology and theoretical computer science. 22nd conference, Kanpur, India, December 12-14, 2002. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2556, 182-193 (2002).
MSC:  68R15 68Q17
PDFBibTeX XMLCite
Full Text: Link

Filter Results by …

Document Type

all top 5

Year of Publication

all top 3

Main Field

Software