@Article{ CPS85, author = {Derek G. Corneil and Yehoshua Perl and Lorna K. Stewart}, title = {A linear recognition algorithm for cographs}, journal = {SIAM Journal on Computing}, year = 1985, volume = 14, number = 4, pages = {926--934} } @Article{ AP90, author = {Gur Saran Adhar and Shietung Peng}, title = {Parallel Algorithms for Cographs and Parity Graphs with Applications}, journal = {Journal of Algorithms}, year = 1990, volume = 11, pages = {252--284} } @Article{ SS94, author = {Gopalakrishnan Sundaram and Steven S. Skiena}, title = {Recognizing Small Subgraphs}, journal = {Networks}, volume = 11, pages = {183--191}, year = 1995, url = {http://citeseer.nj.nec.com/551716.html} } @InProceedings{ PSS02, author = {Itsik Pe'er and Ron Shamir and Roded Sharan}, title = {On the Generality of Phylogenies from Incomplete Directed Characters}, booktitle = {Proceedings of the 8th Scandinavian Workshop on Algorithm Theory (SWAT 2002)}, year = 2002, series = {Lecture Notes in Computer Science}, volume = 2368, pages = {358--367}, publisher = {Springer}, url = {http://www.icsi.berkeley.edu/~roded/publications.html} } @InProceedings{ CK01, author = {Jianer Chen and Iyad A. Kanj}, title = {On Constrained Minimum Vertex Covers of Bipartite Graphs: Improved Algorithms}, booktitle = {Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2001)}, year = 2001, series = {Lecture Notes in Computer Science}, volume = 2204, pages = {55--65}, publisher = {Springer}, url = {http://facweb.cs.depaul.edu/ikanj/research.htm} } @Article{ CKJ01, author = {Jianer Chen and Iyad A. Kanj and Weijia Jia}, title = {Vertex Cover: Further Observations and Further Improvements}, journal = {Journal of Algorithms}, year = 2001, volume = 41, pages = {280--301}, url = {http://facweb.cs.depaul.edu/ikanj/research.htm} } @Article{ McK81, author = {Brendan D. McKay}, title = {Practical graph isomorphism}, journal = {Congressus Numerantium}, year = 1981, volume = 30, pages = {45--87}, url = {http://cs.anu.edu.au/people/bdm/nauty/} } @PhDThesis{ Sha02, author = {Roded Sharan}, title = {Graph Modification Problems and their Applications to Genomic Research}, school = {School of Computer Science}, year = 2002, address = {Tel-Aviv University}, url = {http://www.icsi.berkeley.edu/~roded/publications.html} } @InProceedings{ KR00, author = {Subhash Khot and Venkatesh Raman}, title = {Parameterized Complexity of Finding Subgraphs with Hereditary Properties}, booktitle = {Computing and Combinatorics, 6th Annual International Conference (COCOON 2000)}, year = 2000, address = {Sydney}, series = {Lecture Notes in Computer Science}, volume = 1858, pages = {137--147}, publisher = {Springer}, url = {http://link.springer.de/link/service/series/0558/bibs/1858/18580137.htm} } @Article{ Cai96, author = {Leizhen Cai}, title = {Fixed-parameter tractability of graph modification problems for hereditary properties}, journal = {Information Processing Letters}, year = 1996, volume = 58, pages = {171--176} } @InProceedings{ SST02, author = {Ron Shamir and Roded Sharan and Dekel Tsur}, title = {Cluster Graph Modification Problems}, booktitle = {Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2002)}, series = {Lecture Notes in Computer Science}, volume = 2573, pages = {379--390}, publisher = {Springer}, year = 2002 } @Article{ EC88, author = {Ehab S. El-Mallah and Charles J. Colbourn}, title = {The Complexity of Some Edge Deletion Problems}, journal = {IEEE Transactions on Circuits and Systems}, year = 1988, volume = 35, number = 3, pages = {354--362} } @Book{ SS02, author = {Ron Shamir and Roded Sharan}, title = {Algorithmic Approaches to Clustering Gene Expression Data}, journal = {Current Topics in Computational Molecular Biology}, editor = {T. Jiang et al.}, year = 2002, pages = {269--300}, publisher = {MIT Press} } @Article{ Hir00, author = {Edward A. Hirsch}, title = {New worst-case upper bounds for {SAT}}, journal = {Journal of Automated Reasoning}, year = 2000, volume = 24, number = 4, pages = {397--420} } @InProceedings{ CK02, author = {Jianer Chen and Iyad A. Kanj}, title = {Improved exact algorithms for {MAX-SAT}}, booktitle = {Proceedings of the 5th Latin American Theoretical Informatics (LATIN 2002)}, pages = {341--355}, year = 2002, volume = 2286, series = {Lecture Notes in Computer Science}, publisher = {Springer} } @Article{ NR00b, author = {Rolf Niedermeier and Peter Rossmanith}, title = {New upper bounds for {Maximum Satisfiability}}, journal = {Journal of Algorithms}, year = 2000, volume = 36, pages = {63--88} } @Article{ DP02, author = {Limor Drori and David Peleg}, title = {Faster exact solutions for some {NP}-hard problems}, journal = {Theoretical Computer Science}, year = 2002, volume = 287, number = 2, pages = {473--499} } @InProceedings{ DJ02, author = {Vilhelm Dahlhöf and Peter Jonsson}, title = {An algorithm for counting maximum weighted independent sets and its applications}, booktitle = {Proceedings of the 13th annual ACM-SIAM symposium on Discrete algorithms (SODA 2002)}, pages = {292--298}, year = 2002 } @Article{ Rob86, author = {John Michael Robson}, title = {Algorithms for maximum independent sets}, journal = {Journal of Algorithms}, year = 1986, volume = 7, pages = {425--440} } @Article{ NR03a, author = {Rolf Niedermeier and Peter Rossmanith}, title = {An efficient fixed-parameter algorithm for {3-Hitting Set}}, journal = {Journal of Discrete Algorithms}, year = 2003, volume = 1, pages = {89--102} } @Article{ NR03b, author = {Rolf Niedermeier and Peter Rossmanith}, title = {On efficient fixed-parameter algorithms for {Weighted Vertex Cover}}, journal = {Journal of Algorithms}, volume = {47}, number = {2}, pages = {63--77}, year = 2003 } @Misc{ LVD96, author = {Xavier Leroy and Jérôme Vouillon and Damien Doligez and others}, title = {The {Objective Caml} System}, howpublished = {Available on the web}, year = 1996, note = {\url{http://caml.inria.fr/ocaml/}} } @TechReport{ McK90, author = {Brendan D. McKay}, title = {\textbf{nauty} User's Guide (Version 1.5)}, institution = {Australian National University, Department of Computer Science}, year = 1990, number = {TR-CS-90-02} } @Book{ JD88, author = {Anil K. Jain and Richard C. Dubes}, title = {Algorithms for Clustering Data}, publisher = {Prentice Hall}, year = 1988, address = {Englewood Cliffs, New Jersey} } @Article{ HJ97, author = {Pierre Hansen and Brigitte Jaumard}, title = {Cluster analysis and mathematical programming}, journal = {Mathematical Programming}, year = 1997, volume = 79, pages = {191--215} } @Article{ NSS01, author = {Assaf Natanzon and Ron Shamir and Roded Sharan}, title = {Complexity classification of some edge modification problems}, journal = {Discrete Applied Mathematics}, year = 2001, volume = 113, pages = {109--128} } @Article{ BSY99, author = {Amir Ben-Dor and Ron Shamir and Zohar Yakhini}, title = {Clustering Gene Expression Patterns}, journal = {Journal of Computational Biology}, year = 1999, volume = 6, number = {3/4}, pages = {281--297} } @InProceedings{ SS00, author = {Roded Sharan and Ron Shamir}, title = {{CLICK}: {A} Clustering Algorithm with Applications to Gene Expression Analysis}, booktitle = {Proceedings of the 8th International Conference on Intelligent Systems for Molecular Biology (ISMB 2000)}, publisher = {AAAI Press}, pages = {307--316}, year = {2000} } @Book{ DF99, author = {Rodney G. Downey and Michael R. Fellows}, title = {Parameterized Complexity}, publisher = {Springer}, year = 1999 } @Article{ KST99, author = {Haim Kaplan and Ron Shamir and Robert E. Tarjan}, title = {Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs}, journal = {SIAM Journal on Computing}, year = 1999, volume = 28, number = 5, pages = {1906--1922} } @Article{ MR99, author = {Meena Mahajan and Venkatesh Raman}, title = {Parameterizing above guaranteed values: {MaxSat} and {MaxCut}}, journal = {Journal of Algorithms}, year = 1999, volume = 31, number = 2, pages = {335--354} } @InProceedings{ NR99, author = {Rolf Niedermeier and Peter Rossmanith}, title = {Upper bounds for {Vertex Cover} further improved}, booktitle = {Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1999)}, pages = {561--570}, year = 1999, volume = 1563, series = {Lecture Notes in Computer Science}, publisher = {Springer} } @Article{ AGN01, author = {Jochen Alber and Jens Gramm and Rolf Niedermeier}, title = {Faster exact solutions for hard problems: a parameterized point of view}, journal = {Discrete Mathematics}, year = 2001, volume = 229, pages = {3--27} } @InProceedings{ Fel02, author = {Michael R. Fellows}, title = {Parameterized Complexity: The Main Ideas and Connections to Practical Computing}, booktitle = {Experimental Algorithmics}, pages = {51--77}, year = 2002, volume = 2547, series = {Lecture Notes in Computer Science}, publisher = {Springer} } @Article{ Kul99, author = {Oliver Kullmann}, title = {New methods for 3-{SAT} decision and worst-case analysis}, journal = {Theoretical Computer Science}, year = 1999, volume = 223, number = {1-2}, pages = {1--72} } @Book{ GJ79, author = {Michael R. Garey and David S. Johnson}, title = {Computers and Intractability: A Guide to the Theory of {NP}-Completeness}, publisher = {W. H. Freeman}, year = 1979 } @InProceedings{ GGHN03b, author = {Jens Gramm and Jiong Guo and Falk Hüffner and Rolf Niedermeier}, title = {Graph-Modeled Data Clustering: Fixed-Parameter Algorithms for Clique Generation}, booktitle = {Proceedings of the 5th Italian Conference on Algorithms and Complexity (CIAC 2003)}, pages = {108--119}, year = 2003, series = {Lecture Notes in Computer Science}, volume = 2653, publisher = {Springer} } @InProceedings{ Yan78, author = {Mihalis Yannakakis}, title = {Node- and edge-deletion {NP}-complete problems}, booktitle = {Conference Record of the Tenth Annual ACM Symposium on Theory of Computing}, pages = {253--264}, year = 1978, publisher = {ACM press} } @TechReport{ Rob01, author = {John Michael Robson}, title = {Finding a maximum independent set in time {$O(2^{n/4})$}?}, institution = {Université Bordeaux 1, Département d'Informatique}, year = 2001 } @Article{ NR00a, author = {Rolf Niedermeier and Peter Rossmanith}, title = {A general method to speed up fixed-parameter-tractable algorithms}, journal = {Information Processing Letters}, year = 2000, volume = 73, pages = {125--129} } @MastersThesis{ Nat99, author = {Assaf Natanzon}, title = {Complexity and Approximation of Some Graph Modification Problems}, school = {Department of Computer Science, Tel Aviv University}, year = 1999 } @InProceedings{ Woe03, author = {Gerhard J. Woeginger}, title = {Exact Algorithms for {NP}-Hard Problems: A Survey}, booktitle = {Proceedings of 5th International Workshop on Combinatorial Optimization -- {Eureka}, You Shrink!}, pages = {185--208}, year = 2003, volume = 2570, series = {Lecture Notes in Computer Science}, publisher = {Springer} } @InProceedings{ BR99, author = {Nikhil Bansal and Venkatesh Raman}, title = {Upper bounds for {MaxSat}: further improved}, booktitle = {Proceedings of the 10th International Symposium on Algorithms and Computation (ISAAC 1999)}, pages = {247--258}, year = 1999, volume = 1741, series = {Lecture Notes in Computer Science}, publisher = {Springer} } @TechReport{ HK02, author = {Edward A. Hirsch and Alexander S. Kulikov}, title = {A $2^{n/6.15}$-time algorithm for {X3SAT}}, institution = {Steklov Institute of Mathematics, St. Petersburg}, year = 2002, note = {\url{http://www.pdmi.ras.ru/preprint/2002/02-13.html}} } @Article{ Cai03, author = {Leizhen Cai}, title = {Parameterized Complexity of {Vertex Colouring}}, journal = {Discrete Applied Mathematics}, year = 2003, volume = 127, number = 1, pages = {415--429} } @Article{ LY80, author = {John M. Lewis and Mihalis Yannakakis}, title = {The Node-Deletion Problem for Hereditary Properties is {NP}-Complete}, journal = {Journal of Computer and System Sciences}, year = 1980, volume = 20, number = 2, pages = {219--230} } @InProceedings{ AFF+01, author = {Jochen Alber and Hongbing Fan and Michael R. Fellows and Henning Fernau and Rolf Niedermeier and Fran Rosamond and Ulrike Stege}, title = {Refined search tree technique for {Dominating Set} on planar graphs}, booktitle = {Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science (MFCS 2001)}, pages = {111--122}, year = 2001, volume = 2136, series = {Lecture Notes in Computer Science}, publisher = {Springer} } @Book{ BLS99, author = {Andreas Brandstädt and Van Bang Le and Jeremy P. Spinrad}, title = {Graph Classes: a Survey}, publisher = {SIAM Monographs on Discrete Mathematics and Applications}, year = 1999, note = {See also \emph{Information system on graph class inclusions}, \url{http://wwwteo.informatik.uni-rostock.de/isgci/}} } @Misc{ LDG02, author = {Xavier Leroy and Damien Doligez and Jacques Garrigue and Didier Rémy and Jérôme Vouillon}, title = {The {Objective Caml} system -- Documentation and user's manual}, year = 2002, note = {\url{http://caml.inria.fr/ocaml/htmlman/}} } @Book{ CMP00, author = {Emmanuel Chailloux and Pascal Manoury and Bruno Pagano}, title = {Développement d'applications avec {Objective Caml}}, publisher = {O'Reilly France}, year = 2000, note = {English translation available at \url{http://caml.inria.fr/oreilly-book/}} } @InProceedings{ BBC02, author = {Nikhil Bansal and Avrim Blum and Shuchi Chawla}, title = {Correlation Clustering}, booktitle = {Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2002)}, publisher = {IEEE Computer Society}, pages = {238--247}, year = 2002 } @Article{ CJL03, author = {Zhi-Zhong Chen and Tao Jiang and Guohui Lin}, title = {Computing Phylogenetic Roots with Bounded Degrees and Errors}, journal = {SIAM Journal on Computing}, year = 2003, volume = 32, number = 4, pages = {864--879}, note = {Extended abstract appeared in Proceedings of the 7th International Workshop on Algorithms and Data Structures (WADS 2001)} } @InProceedings{ CKX03, author = {Jianer Chen and Iyad A. Kanj and Ge Xia}, title = {Labeled Search Trees and Amortized Analysis: Improved Upper Bounds for {NP}-hard Problems}, booktitle = {Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC 2003)}, year = 2003, note = {To appear} } @InProceedings{ CGW03, author = {Moses Charikar and Venkatesan Guruswami and Anthony Wirth}, title = {Clustering with Qualitative Information}, booktitle = {Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2003)}, publisher = {IEEE Computer Society}, year = 2003, note = {To appear} } @InProceedings{ DI03, author = {Erik D. Demaine and Nicole Immorlica}, title = {Correlation Clustering with Partial Information}, booktitle = {Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2003)}, year = 2003, note = {To appear} } @InProceedings{ EF03, author = {Dotan Emanuel and Amos Fiat}, title = {Correlation Clustering -- Minimizing Disagreements on Arbitrary Weighted Graphs}, booktitle = {Proceedings of the 11th Annual European Symposium on Algorithms (ESA 2003)}, year = 2003, series = {Lecture Notes in Computer Science}, volume = 2832, pages = {208--220}, publisher = {Springer} } @Article{ KM86, author = {Mirko K\v{r}ivánek and Jaroslav Morávek}, title = {{NP}-Hard Problems in Hierarchical-Tree Clustering}, journal = {Acta Informatica}, year = 1986, volume = 23, number = 3, pages = {311--323} } @InProceedings{ Dow03, author = {Rodney G. Downey}, title = {Parameterized complexity for the skeptic}, booktitle = {Proceedings of the 18th IEEE Annual Conference on Computational Complexity}, pages = {147--169}, year = 2003 } @Article{ GHNR03, author = {Jens Gramm and Edward A. Hirsch and Rolf Niedermeier and Peter Rossmanith}, title = {Worst-case upper bounds for {MAX-2-SAT} with an application to {MAX-CUT}}, journal = {Discrete Applied Mathematics}, year = 2003, volume = 130, number = 2, pages = {139--155} } @InProceedings{ KP02, author = {Iyad A. Kanj and Ljubomir Perkovi\'c}, title = {Improved Parameterized Algorithms for Planar Dominating Set}, booktitle = {Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS 2002)}, year = 2002, series = {Lecture Notes in Computer Science}, volume = 2420, publisher = {Springer}, pages = {399--410} } @Article{ HK92, author = {Lars Hagen and Andrew B. Kahng}, title = {New spectral methods for ratio cut partitioning and clustering}, journal = {IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems}, year = 1992, volume = 11, number = 9, pages = {1074­-1085} } @Article{ WL93, author = {Zhenyu Wu and Richard Leahy}, title = {An optimal graph theoretic approach to data clustering: theory and its application to image segmentation}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, year = 1993, volume = 15, number = 11, pages = {1101--1113} } @Article{ GVSS02, author = {Irit Gat-Viks and Roded Sharan and Ron Shamir}, title = {Scoring Clustering Solutions by their Biological Relevance}, journal = {Bioinformatics}, year = 2003, note = {To appear} } @InProceedings{ GGHN03a, author = {Jens Gramm and Jiong Guo and Falk Hüffner and Rolf Niedermeier}, title = {Automated Generation of Search Tree Algorithms for Graph Modification Problems}, booktitle = {Proceedings of the 11th Annual European Symposium on Algorithms (ESA 2003)}, year = 2003, series = {Lecture Notes in Computer Science}, volume = 2832, pages = {642--653}, publisher = {Springer} } @Article{ FN01, author = {Henning Fernau and Rolf Niedermeier}, title = {An efficient exact algorithm for {Constraint Bipartite Vertex Cover}}, journal = {Journal of Algorithms}, year = 2001, volume = 38, number = 2, pages = {374--410} } @Book{ HHS98b, author = {Teresa W. Haynes and Stephen T. Hedetniemi and Peter J. Slater}, title = {Fundamentals of Domination in Graphs}, publisher = {Marcel Dekker}, year = 1998, volume = {208}, series = {Pure and Applied Mathematics} } @Book{ HHS98a, editor = {Teresa W. Haynes and Stephen T. Hedetniemi and Peter J. Slater}, title = {Domination in Graphs: Advanced Topics}, publisher = {Marcel Dekker}, year = 1998, volume = 209, series = {Pure and Applied Mathematics} } @InProceedings{ NS03, author = {Sergey I. Nikolenko and Alexander V. Sirotkin}, title = {Worst-case upper bounds for {SAT}: automated proof}, booktitle = {15th European Summer School in Logic Language and Information (ESSLLI 2003), Student Session}, year = 2003 } @Unpublished{ FK03, author = {Sergey S. Fedin and Alexander S. Kulikov}, title = {Automated proofs of upper bounds on the running time of splitting algorithms}, note = {Manuscript, Steklov Institute of Mathematics, St. Petersburg}, year = {2003}, month = {September} } @InProceedings{ Sch01, author = {Uwe Schöning}, title = {New Algorithms for {$k$-SAT} Based on the Local Search Principle}, booktitle = {Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science (MFCS 2001)}, pages = {87--95}, year = 2001, volume = 2136, series = {Lecture Notes in Computer Science}, publisher = {Springer} } @TechReport{ DHIV01, author = {Evgeny Dantsin and Edward A. Hirsch and Sergei Ivanov and Maxim Vsemirnov}, title = {Algorithms for {SAT} and Upper Bounds on Their Complexity}, institution = {Electronic Colloquium on Computational Complexity}, year = 2001, number = {TR01-012} }