@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}
}