@String{CABIOS = {Comput. Appl. Biosci.}}
@String{G = {Genomics}}
@String{GR = {Genome Research}}
@String{ISMB = {Intelligent Systems in Molecular Biology (ISMB)}}
@String{JMB = {Journal of Molecular Biology}}
@String{MBE = {Molecular Biology and Evolution}}
@String{NAR = {Nucleic Acids Research}}
@String{NG = {Nature Genetics}}
@String{PNAS = {Proceedings of the National Academy of Sciences}}
@String{PSB = {Proceedings of the Pacific Symposium on Biocomputing}}
@String{RECOMB = {International Conference on Computational Molecular Biology (RECOMB)}}
@String{UM = {Unpublished manuscript}}
@String{DAM = {Discrete Applied Mathematics}}

@String{C = {Combinatorica}}
@String{CN = {Congress Numerantium}}
@String{DCG = {Discrete and Computational Geometry}}
@String{DM = {Discrete Mathematics}}
@String{JADM = {SIAM Journal on Algebraic and Discrete Methods}}
@String{JDM = {SIAM Journal on Discrete Mathematics}}
@String{JAM = {SIAM Journal on Applied Mathematics}}
@String{JOC = {SIAM Journal on Computing}}
@String{JGT = {Journal of Graph Theory}}
@String{TCS = {Theoretical Computer Science}}
@String{IPL = {Information Processing Letters}}
@String{JACM = {Journal of the ACM (JACM)}}

@article{Human2001,
title = {The {S}equence of the {H}uman {G}enome},
author = {J. Craig Venter and M. D. Adams and E. W. Myers and P. Li and R. J.
Mural and G. G. Sutton and H. O. Smith and M. Yandell and C. A. Evans and R.
A. Holt and J. D. Gocayne and P. Amanatides and R. M. Ballew and D. H. Huson
and J. Russo Wortman and Q. Zhang and C. Kodira and X. H. Zheng and L. Chen
and M. Skupski and G. Subramanian and P. D. Thomas and J. Zhang and G. L.
Gabor Miklos and C. Nelson and S. Broder and A. G. Clark and J. Nadeau and
V. A. McKusick and N. Zinder and A. J. Levine and R. J. Roberts and M. Simon
and C. Slayman and M. Hunkapiller and R. Bolanos and A. Delcher and I. Dew
and D. Fasulo and M. Flanigan and L. Florea and A. Halpern and S.
Hannenhalli and S. Kravitz and S. Levy and C. Mobarry and K. Reinert and K.
Remington and J. Abu-Threideh and E. Beasley and K. Biddick and V. Bonazzi
and R. Brandon and M. Cargill and I. Chandramouliswaran and R. Charlab and
K. Chaturvedi and Z. Deng and V. Di Francesco and P. Dunn and K. Eilbeck and
C. Evangelista and A. E. Gabrielian and W. Gan and W. Ge and F. Gong and Z.
Gu and P. Guan and T. A. Heiman and M. E. Higgins and R-R. Ji and Z. Ke and
K. A. Ketchum and Z. Lai and Y. Lei and Z. Li and J. Li and Y. Liang and X.
Lin and F. Lu and G. V. Merkulov and N. Milshina and H. M. Moore and A. K
Naik and V. A. Narayan and B. Neelam and D. Nusskern and D. B. Rusch and S.
Salzberg and W. Shao and B. Shue and J. Sun and Z. Yuan Wang and A. Wang and
X. Wang and J. Wang and M-H. Wei and R. Wides and C. Xiao and C. Yan and A.
Yao and J. Ye and M. Zhan and W. Zhang and H. Zhang and Q. Zhao and L. Zheng
and F. Zhong and W. Zhong and S. C. Zhu and S. Zhao and D. Gilbert and S.
Baumhueter and G. Spier and C. Carter and A. Cravchik and T. Woodage and F.
Ali and H. An and A. Awe and D. Baldwin and H. Baden and M. Barnstead and I.
Barrow and K. Beeson and D. Busam and A. Carver and A. Center and M. Lai
Cheng and L. Curry and S. Danaher and L. Davenport and R. Desilets and S.
Dietz and K. Dodson and L. Doup and S. Ferriera and N. Garg and A.
Gluecksmann and B. Hart and J. Haynes and C. Haynes and C. Heiner and S.
Hladun and D. Hostin and J. Houck and T. Howland a. Chinyere Ibegwam and J.
Johnson and F. Kalush and L. Kline and S. Koduru and A. Love and F. Mann and
D. May and S. McCawley and T. McIntosh and I. McMullen and M. Moy and L. Moy
and B. Murphy and K. Nelson and C. Pfannkoch and E. Pratts and V. Puri and
H. Qureshi and M. Reardon and R. Rodriguez and Y-H. Rogers and D. Romblad
and B. Ruhfel and R. Scott and C. Sitter and M. Smallwood and E. Stewart and
R. Strong and E. Suh and R. Thomas and N. Ni Tint and S. Tse and C. Vech and
G. Wang and J. Wetter and S. Williams and M. Williams and S. Windsor and E.
Winn-Deen and K. Wolfe and J. Zaveri and K. Zaveri and J. F. Abril and R.
Guigo � and M. J. Campbell and K. V. Sjolander and B. Karlak and A.
Kejariwal and H. Mi and B. Lazareva and T. Hatton and A. Narechania and K.
Diemer and A. Muruganujan and N. Guo and S. Sato and V. Bafna and S. Istrail
and R. Lippert and R. Schwartz and B. Walenz and S. Yooseph and D. Allen and
A. B. and J. Baxendale and L. Blick and M. Caminha and J. Carnes-Stine and
P. Caulk and Y-H. Chiang and M. Coyne and C. Dahlke and A. Deslattes Mays
and M. Dombroski and M. Donnelly and D. Ely and S. Esparham and C. Fosler
and H. Gire and S. Glanowski and K. Glasser and A. Glodek and M. Gorokhov
and K. Graham and B. Gropman and M. Harris and J. Heil and S. Henderson and
J. Hoover and D. Jennings and C. Jordan and J. Jordan and J. Kasha and L.
Kagan and C. Kraft and A. Levitsky and M. Lewis and X. Liu and J. Lopez and
D. Ma and W. Majoros and J. McDaniel and S. Murphy and M. Newman and T.
Nguyen and N. Nguyen and M. Nodell and S. Pan and J. Peck and W. Rowe and R.
Sanders and J. Scott and M. Simpson and T. Smith and A. Sprague and T.
Stockwell and R. Turner and E. Venter and M. Wang and M. Wen and D. Wu and
M. Wu and A. Xia and A. Zandieh and X. Zhu},
volume = 291,
pages = {1145-1434},
year = 2001
}

@article{PW93,
 author = {P. A. Pevzner and M. S. Waterman},
 title = {Generalized Sequence Alignment and Duality},
 journal = {Advances in Applied Mathematics},
 pages = {139-171},
 year = {1993},
 volume = {14},
 annote = {CB3}
}

@Manual{repeatmasker,
 title = {RepeatMasker},
 OPTkey = {},
 author = {A.~F.~A. Smit and P Green},
 OPTorganization = {},
 address = {http://ftp.genome.washington.edu/cg-bin/RepeatMasker},
 OPTedition = {},
 OPTmonth = {},
 year = {1995},
 OPTnote = {},
 OPTannote = {}
}

@Article{altschul90,
 author = {S.~F. Altschul and W. Gish and W. Miller and E.~W. Myers 
 and D.~J. Lipman},
 title = {Basic local alignment search tool},
 journal = JMB,
 year = {1990},
 OPTkey = {},
 volume = {215},
 OPTnumber = {},
 pages = {403-410},
 OPTmonth = {},
 OPTnote = {},
 OPTannote = {}
}

@incollection{atteson,
author = {K. Atteson},
title = {The performance of neighbor-joining algorithms of
 phylogeny reconstruction},
note = {Cocoon '97},
booktitle = {Lecture Notes in Computer Science, 1276},
editor = {Tao Jiang and D. T. Lee},
publisher = {Springer-Verlag},
pubaddress = {Berlin}, 
pages = {101-110},
year = 1997
}
 
@article{BandeltDress92,
author = {H.-J. Bandelt and A. W. M. Dress},
title = {A canonical decomposition theory for metrics on a finite set},
journal = {Advances in Mathematics},
volume = {92},
pages = {47-105},
year = 1992
}

@article{BandeltDress92b,
author = {H.-J. Bandelt and A.W.M. Dress},
title = {Split Decomposition: A new and useful
approach to phylogenetic analysis of distance data},
journal = {Molecular Phylogenetics and Evolution},
volume = {1(3)},
pages = {242-252},
year = 1992
}

@incollection{BG,
author = {V. Berry and O. Gascuel},
title = {Inferring evolutionary trees with strong combinatorial evidence},
note = {COCOON '97},
booktitle = {Lecture Notes in Computer Science, 1276},
editor = {Tao Jiang and D. T. Lee},
publisher = {Springer-Verlag},
pubaddress = {Berlin},
pages = {111-123},
year = 1997
}

@incollection{twostrikes,
author = {H. Bodlaender and M. Fellows and T. Warnow},
title = {Two strikes against perfect phylogeny},
note = {Proceedings, International Colloquium on
Automata, Languages and Programming},
booktitle = {Lecture Notes in Computer Science, 623},
publisher = {Springer-Verlag},
pubaddress = {Berlin}, 
pages = {273-283},
year = 1992
}

@misc{otr,
author = {M. Bonet and M. A. Steel and T. Warnow and S. Yooseph},
title = {Better methods for solving parsimony and compatibility},
note = {Proceedings ``RECOMB'98''},
year = 1998
}

@article{weighbor,
author = {W. J. Bruno and N. D. Socci and A. L. Halpern},
title = {Weighted {Neighbor Joining}: A Likelihood-Based Approach to
Distance-Based 
Phylogeny Reconstruction},
journal = MBE,
volume = 17,
number = 1,
pages = {189-197},
year = 2000
}

@incollection{buneman.dist,
author = {P. Buneman},
title = {The recovery of trees from measures of dissimilarity},
booktitle = {Mathematics in the Archaeological and Historical Sciences},
editor = {F. R. Hodson and D. G. Kendall and P. Tautu},
publisher = {Edinburgh University Press},
pages = {387-395},
year = 1971
}
 
@unpublished{CGG,
author = {M. Cryan and L. Goldberg and P. Goldberg},
title = {Evolutionary trees can be learned in polynomial time
in the two-state general Markov model},
note = {Submitted to FOCS '98},
year = 1998
}


@misc{hgt,
author = {M. Csuros and M.-Y. Kao},
title = {Recovering evolutionary trees through harmonic greedy triplets},
note = {Proceedings SODA'99},
pages = {261-270},
year = 1999
}

@article{Day.consensus,
author = {W. H. E. Day},
title = {Optimal algorithms for comparing trees with labelled leaves},
journal = {Journal of Classification},
volume = {2},
pages = {7-28},
year = 1995
}

@unpublished{essw.georgetown,
author = {P. L. Erd\"os and K. Rice and M. A. Steel and L. Sz\'ekely
and T. Warnow}, 
title = {The Short Quartet Method},
note = {To appear in:
Mathematical Modeling and Scientific Computing, Principia Scientia},
year = 1998
}

@incollection{essw-icalp,
author = {P. L. {Erd\H os} and M. A. Steel and L. A. {Sz\'ekely}
and T. Warnow},
title = {Constructing big trees from short sequences},
note = {ICALP'97},
editor = {G. Goos and J. Hartmanis and J. van Leeuwen},
booktitle = {Lecture Notes in Computer Science},
volume = {1256},
year = 1997
}

@article{essw-ai,
author = {P. {Erd\H os} and M. A. Steel and L. Szekely and T. Warnow},
title = {Local quartet splits of a binary tree infer
all quartet splits via one dyadic inference rule},
journal = {Computers and Artificial Intelligence},
volume = {16},
number = {2}, 
pages = {217-227},
year = 1997
}

@article{essw-rsa,
author = {P. L. {Erd\H os} and M. A. Steel and L. A. {Sz\'ekely}
and T. Warnow},
title = {A few logs suffice to build (almost) all trees {I}},
journal = {Random Structures and Algorithms},
volume = 14,
number = 2,
pages = {153-184},
year = 1999
}

@unpublished{essw-tcs,
author = {P. L. {Erd\H os} and M. A. Steel and L. A. {Sz\'ekely}
and T. Warnow},
title = {A few logs suffice to build (almost) all trees {II}},
note = {to appear in Theor. Comp. Sci.},
year = 1997
}

@article{FKW,
author = {M. Farach and S. Kannan and T. Warnow},
title = {A Robust Model for Finding Optimal Evolutionary Trees},
journal = {Algorithmica},
note = {Special issue on Computational Biology},
volume = 13,
number = 1,
pages = {155--179},
year = 1995
}

@article{misleading,
author = {J. Felsenstein},
title = {Cases in which parsimony or compatibility
methods will be positively misleading},
journal = {Systematic Zoology},
volume = {27},
pages = {401-410},
year = 1978
}

@article{felsenstein.review,
author = {J. Felsenstein},
title = {Phylogenies from molecular sequences: inference and reliability},
journal = {Annu. Rev. Genet.},
volume = {22},
pages = {521-565},
year = 1988
}

@unpublished{Phylip,
author = {J. Felsenstein},
title = {{PHYLIP} (Phylogeny Inference Package) version 3.6},
note = {Distributed by the author. Department of Genome Sciences, University of
Washington, Seattle},
year = 2004
}

@article{bio-nj,
author = {O. Gascuel},
title = {{BIONJ}: An improved version of the {NJ} algorithm based on a
simple model of sequence data},
journal = {Mol. Biol. Evol.},
volume = 14,
pages = {685-695},
year = 1997
}

@book{Golumbic,
author = {Martin C. Golumbic},
title = {Algorithmic Graph Theory and Perfect Graphs},
publisher = {Academic Press Inc},
year = 1980
}

@unpublished{Gusfield91,
author = {D. Gusfield},
title = {Efficient methods for multiple sequence
alignment with guaranteed error bounds},
note = {Computer Science Division, UC Davis, Technical Report CSE 91-4},
year = 1991
}

@unpublished{GW1996,
author = {D. Gusfield and L. Wang},
title = {New uses for uniform lifted alignments},
note = {Computer Science Division, UC Davis, Technical Report CSE 96-4.},
year = 1996
}

@article{hillis.nature,
author = {D. Hillis},
title = {Inferring complex phylogenies},
journal = {Nature},
volume = {383},
month = {12 September},
pages = {130-131},
year = 1996
}

@article{SplitsTree98,
author = {D. H. Huson},
title = {{SplitsTree}: A Program for Analyzing and Visualizing Evolutionary
Data},
journal = {Bioinformatics},
volume = {14(10)},
pages = {68-73},
year = 1998
}

@inproceedings{DCM:Alex1998,
author = {D. H. Huson and S. Nettles and L. Parida and T. Warnow
and S. Yooseph},
title = {The Disk-Covering Method for Tree Reconstruction},
booktitle = {Proceedings of ``Algorithms and Experiments'' (ALEX98),
Trento},
pages = {62-75},
year = 1998
}

@article{Hybrid2000,
author = {D. H. Huson and S. Nettles and K. Rice and T. Warnow},
title = {Hybrid tree reconstruction methods}, 
journal = {J. Experimental Algorithms},
volume = 4,
pages = 5,
year = 2000
}

@inproceedings{Hybrid:WAE1998,
author = {D. H. Huson and S. Nettles and K. Rice and T. Warnow},
title = {Hybrid tree reconstruction methods}, 
booktitle = {Proceedings of the ``Workshop on Algorithm Engineering'',
{Saarbr\"ucken}},
pages = {172-192},
year = 1998
}

@inproceedings{DCM:Recomb1999,
author = {D. H. Huson and S. Nettles and T. Warnow},
title = {Obtaining Highly Accurate Topology Estimates of
Evolutionary Trees From Very Short Sequences},
note = {Proceedings of the Third International Conference on Research
in Computational Molecular Biology (RECOMB)},
pages = {198--207},
year = 1999
}

@unpublished{HusonSmithWarnow99,
author = {D. Huson and K. A. Smith and T. Warnow},
title = {Correcting Large Distances for Phylogenetic Reconstruction},
note = {Submitted to: WAE'99},
year = 1999
}

@incollection{JukesCantor1969,
author = {T. H. Jukes and C. R. Cantor},
title = {Evolution of Protein Molecules},
editor = {H. N. Munro},
booktitle = {Mammalian Protein Metabolism},
publisher = {Academic Press},
pubaddress = {New York}, 
pages = {21-132},
year = 1969
}

@article{KF,
author = {M. Kuhner and J. Felsenstein},
title = {A simulation comparison of phylogeny algorithms under equal and unequal
evolutionary rates},
journal = {Mol. Biol. Evol.},
volume = {11},
pages = {459-468},
year = 1994
}

@article{maddison1,
author = { D. R. Maddison and M. Ruvolo and D. L. Swofford},
title = {Geographic origins of human mitochondrial {DNA}: phylogenetic evidence
from control region sequences},
journal = {Systematic Zoology },
volume = {41},
pages = {111-124},
year = 1992
}

@article{MWW,
author = {F. R. McMorris and T. Warnow and T. Wimer},
title = {Triangulating vertex-colored graphs},
journal = {SIAM J. of Discrete Mathematics},
volume = {7},
number = 2,
pages = {296-306},
year = 1994
}

@article{Modi99,
author = {W. Modi and T. Yoshimura},
title = {Isolation of novel {GRO} genes and a
phylogenetic analysis of the {CXC} chemokine subfamily in mammals},
journal = {Mol. Biol. Evol.},
volume = 16,
pages = {180-193},
year = 1999
}

@article{Page1998,
author = {R. D. Page and P. L. Lee and S. A. Becher and R. Griffiths and
D. H. Clayton},
title = {A different tempo of mitochondrial {DNA} evolution in birds and their
parasitic lice},
journal = {Mol. Phylogenet. Evol.},
volume = 9,
number = 2,
pages = {276-293},
year = {1998}
}

@article{Paladin1998,
author = {F. J. Paladin and O. T. Monzon and H. Tsuchie and M. R. Aplasca and
G. H. Learn and T. Kurimura},
title = {Genetic subtypes of {HIV-1} in the {Philippines}},
journal = {AIDS},
volume = 12,
number = 3,
pages = {291-300},
year = {1998}
}

@article{phillips.warnow,
author = {C. A. Phillips and T. Warnow},
title = {The Asymmetric Median Tree: a new model for building consensus trees},
journal = {Discrete Applied Mathematics},
note = {Special Issue on Computational Molecular Biology},
volume = {71},
pages = {311-335},
year = 1996
}

@article{purvis,
author = {A. Purvis and D. Quicke},
journal = {Trends in Ecology and Evolution},
volume = {12},
number = {2},
pages = {49-50},
year = 1997
}

@article{SEQGEN,
author = {A. Rambaut and N. C. Grassly},
title = {An application for the Monte Carlo simulation of {DNA} sequence
evolution along phylogenetic trees},
journal = { Comput. Appl. Biosci.},
volume = 13,
number = 3,
pages = {235-238},
year = 1997
}

@unpublished{RHYN98,
author = {B. Rannala and J. Huelsenbeck and Z. Yang and R. Nielsen},
title = {Taxon Sampling and the Accuracy of Large Phylogenies},
note = {To appear in: Systematic Biology},
year = 1998
}

@misc{ecat,
author = {K. Rice},
title = {{ECAT}, an evolution simulator},
note = {http://www.cis.upenn.edu/$\sim$krice},
year = 1997
}

@article{Rice1997,
author = {K. A. Rice and M. J. Donoghue and R. G. Olmstead},
title = {Analyzing large data sets: {\em rbc}{L} 500 revisited},
journal = {Syst. Biol.},
volume = 46,
number = 3,
pages = {554-563},
year = {1997}
}

@incollection{cocoon,
author = {K. Rice and T. Warnow},
title = {Parsimony is Hard to Beat!},
note = {COCOON '97},
booktitle = {Lecture Notes in Computer Science, 1276},
editor = {Tao Jiang and D. T. Lee},
publisher = {Springer-Verlag},
pubaddress = {Berlin},
pages = {124-133},
year = 1997
}

@article{Rogers99,
author = { A. J. Rogers and O. Sandblom and W. F. Doolittle and H. Philippe},
title = {An evaluation of elongation factor 1-alpha as a phylogenetic marker
for eukaryotes},
journal = {Mol. Biol. Evol},
volume = 16,
pages = {218-233},
year = 1999
}

@article{protein.structure,
author = {B. Rost and C. Sander},
title = {Prediction of protein secondary structure at better than 70\%
accuracy},
journal = {Journal of Molecular Biology},
volume = {232},
pages = {584-599},
year = 1993
}

@article{NJ,
author = {N. Saitou and M. Nei},
title = {The {Neighbor-Joining} method: a new method for reconstructing
phylogenetic trees},
journal = MBE,
volume = {4},
pages = {406-425},
year = 1987 
}

@article{SH,
author = {M. Sch\"oniger and A. von Haeseler},
title = {Performance of maximum likelihood, neighbor-joining, and maximum
parsimony methods when sequence sites are not independent},
journal = {Syst. Biol.},
volume = {44},
number = {4},
pages = {533-547},
year = 1995
}

@article{Skoufos1999,
author = {E. Skoufos and M. D. Healy and M. S. Singer and P. M. Nadkarni
and P. L. Miller and G. M. Shepherd},
title = {Olfactory Receptor Database: a database of the largest eukaryotic
gene
family},
journal = {Nucl. Acids Res.},
volume = 27,
number = 1,
pages = {343-345},
year = {1999}
}

@article{Soltis,
author = {D. E. Soltis and P. S. Soltis and D. L. Nickrent and L. A. Johnson
and W. J. Hahn and S. B. Hoot and J. A. Sweere and R. K. Kuzoff
and K. A. Kron and M. W. Chase and S. M. Swensen and E. A. Zimmer
and S.-M. Chaw and L. J. Gillespie and W. J. Kress and K. J. Sytsma},
title = { Angiosperm phylogeny inferred from 18S ribosomal {DNA}
sequences},
journal = {Annals of the Missouri Botanical Garden},
volume = {84},
pages = {1-49},
year = 1997
}

@article{Sourdis,
author = {J. Sourdis and M. Nei},
title = {Relative efficiencies of the maximum parsimony and distance-matrix
methods in obtaining the correct phylogenetic tree},
journal = {Mol. Biol. Evol.},
volume = {5},
number = {3},
pages = {293-311},
year = 1996
}



@article{tree.of.life,
author = {M. L. Sogin and G. Hinkle and D. D. Leipe},
title = {Universal tree of life},
journal = {Nature},
volume = {362},
pages = {795},
year = 1993
}



@article{nohope,
author = {M. A. Steel and L. A. {Sz\'ekely} and M. D. Hendy},
title = {Reconstructing trees when sequence sites evolve at variable rate},
journal = {J. Computational Biology},
volume = {1},
number = {2}, 
pages = {153-163},
year = 1994
}

@article{Steel:1992,
author = {M. Steel},
title = {The complexity of reconstructing trees from qualitative characters and
subtrees},
journal = {J. Classification},
volume = {9},
pages = {91-116},
year = 1992
}

@article{Steel:Recovering,
author = {M. Steel},
title = {Recovering a tree from the leaf colourations
it generates under a Markov model},
journal = {Applied Math Letters},
volume = {7},
number = {2},
pages = {19-24},
year = 1994
}




@article{SaitouImanishi89,
author = {N. Saitou and T. Imanishi},
title = {Relative efficiencies of the {Fitch}-{Margoliash}, maximum parsimony,
maximum likelihood, minimum evolution, and neighbor-joining methods
of phylogenetic tree construction in obtaining the correct tree},
journal = {Mol. Biol. Evol.},
volume = {6},
pages = {514-525},
year = 1989
}

@article{SourdisNei,
author = {J. Sourdis and M. Nei},
title = {Relative efficiencies of the maximum parsimony and distance-matrix
methods in obtaining the correct phylogenetic tree},
journal = {Mol. Biol. Evol.},
volume = 5,
number = 3,
pages = {393-311},
year = 1996
}

@article{Arndt.nj,
author = {K. Strimmer and A. von Haeseler},
title = {Accuracy of Neighbor-Joining for n-Taxon Trees},
journal = {Syst. Biol.},
volume = {45},
number = {4},
pages = {516-523},
year = 1996
}

@misc{PAUP,
author = {D. L. Swofford},
title = {{PAUP$^\ast$}: Phylogenetic analysis using parsimony
($\ast$: and other methods), version 4.2},
publisher = {Sinauer Assoc.},
pubaddress = {Sunderland Mass.},
year = 2000
}

@incollection{SOWH1996,
author = {D. L. Swofford and G. J. Olsen and P. J. Waddell and
D. M. Hillis},
title = {Chapter 11: Phylogenetic inference},
editor = {D. M. Hillis and C. Moritz and B. K. Mable},
booktitle = {Molecular Systematics},
publisher = {Sinauer Associates, Inc.},
edition = {2nd},
publaddr = {Sunderland},
pages = {407--514},
year = 1996
}

@article{Sullivan1994,
author = {S.~L. Sullivan and K.~J. Ressler and L.~B. Buck},
title = {Odorant receptor diversity and patterned gene expression in
the mammalian olfactory epithelium},
journal = {Prog. Clin. Biol. Res.},
volume = 390,
pages = {75-84},
year = 1994
}

@article{Templeton95,
author = {A. R. Tempelton},
title = {A cladistic analysis of phenotypic associations with haplotypes
inferred from restriction endonuclease mapping or {DNA} sequencing.
{V}. {A}nalysis of case/control sampling designs: {Alzheimer's} disease and
the apoprotein {E} locus},
journal = {Genetics},
volume = 140,
pages = {403-409},
year = 1995
}


@article{TuffleySteel97,
author = {C. Tuffley and M.~A. Steel},
title = {Links between maximum likelihood and maximum
parsimony under a simple model of site substitution},
journal = {Bulletin of Mathematical Biology},
volume = 59,
number = 3,
pages = {581-607},
year = 1997
}

@article{vawter,
author = {L. Vawter and W. Brown},
title = {Nuclear and mitochondrial {DNA} comparisons reveal extreme 
rate variation in the molecular clock},
journal = {Science},
volume = {234},
pages = {194-196},
year = 1986
}

@phdthesis{vawter91,
author = {L. Vawter},
title = {Evolution of the Blattodea and of the small subunit
ribosomal {RNA} gene},
school = {Univ. of Michigan, Ann Arbor MI USA},
year = 1991
}

@article{warnow,
author = {T. Warnow},
title = {Tree compatibility and inferring evolutionary history},
journal = {J. of Algorithms},
volume = 16,
pages = {388-407},
year = 1994
}

@unpublished{warnow.balaton,
author = {T. Warnow},
title = {Some combinatorial problems in Phylogenetics},
note = {To appear in the
proceedings of the International Colloquium on Combinatorics
and Graph Theory, Balatonlelle, Hungary, July 15-20,
eds. A. Gy\'arf\'as, L. Lov\'asz, L. A. Sz\'ekely, in a forthcoming
volume of Bolyai Society Mathematical Studies},
year = 1996
}

@article{waterman,
author = {M.~S. Waterman and T.~F. Smith and W.~A. Beyer},
title = {Additive evolutionary trees},
journal = {Journal Theoretical Biol.},
volume = {64},
pages = {199-213},
year = 1977
}

@article{Watson1997,
author = {E. Watson and P. Forster and M. Richards and H.-J. Bandelt},
title = {Mitochondrial footprints of human expansions in Africa},
journal = {Am. J. Hum. Genet.},
volume = 61,
number = 3,
pages = {691-704},
year = {1997}
}

@article{bayes,
author = {Z. Yang and B. Rannala},
title = {Bayesian phylogenetic inference using {DNA} sequences: a 
Markov Chain Monte Carlo Method},
journal = {Mol. Biol. Evol.},
year = 1997
}

@article{GenBank,
title = {GenBank},
author = {D.~A. Benson and I. Karsch-Mizrachi and D.~J. Lipman and J. Ostell 
and B.~A. Rapp and D.~L. Wheeler},
journal = {Nucleic Acids Research},
volume = 28,
number = 1,
pages = {15-8},
year = 2000
}

@article{DrosophilaAssembly,
title = {A Whole-Genome Assembly of {Drosophila}},

author = {E.~W. Myers and G.~G. Sutton and A.~L. Delcher and I.~M. Dew
and D.~P. Fasulo and M.~J. Flanigan and S.~A. Kravitz and C.~M. Mobarry
and K.~H.~J. Reinert and K.~A. Remington and E.~L. Anson
and R.~A. Bolanos and H-H. Chou and C.~M. Jordan and A.~L. Halpern 
and S. Lonardi and E.~M. Beasley and R.~C. Brandon
and L. Chen and P.~J. Dunn and Z. Lai and Y. Liang and D.~R. Nusskern and 
M. Zhan and Q. Zhang and X. Zheng and G.~M.
Rubin and M.~D. Adams and J.~C. Venter},

journal = {Science},
pages = {2196-2204},
volume = 287,
year = 2000
}



@article{Compartmentalized,
author = {
D.~H. Huson and K. Reinert
and S.~A. Kravitz and K.~A. Remington
and A.~L. Delcher and I.~M. Dew
and M.~Flanigan
and A.~L. Halpern
and Z. Lai
and C. M.~Mobarry
and G.~G. Sutton and E.~W. Myers},
title = {Design of a Compartmentalized Shotgun Assembler for the Human
Genome},
volume = 17,
pages = {132--139},
journal = {Bioinformatics},
note = {Proceedings of ISMB 2001},
year = 2001
}

@article{WeberMyers97,
title = {Human whole-genome shotgun sequencing},
author = {J.~L. Webber and E.~W. Myers},
journal = {Genome Research},
volume = 7,
number = 5,
pages = {401--409},
year = 1997
}

@article{SangerNicklenCoulson77,
author = {F. Sanger and S. Nicklen and A.~R. Coulson},
title = {{DNA} sequencing with chain-terminating inhibitors},
journal = {Proceedings of the National Academy of Sciences},
volume = 74,
number = 12,
pages = {5463--5467},
year = 1977
}

@article{Sanger82,
author = {F. Sanger and A.~R. Coulson and G.~F. Hong and D.~F. Hill and G.~B.
Petersen},
title = {Nucleotide sequence of bacteriophage $\lambda$ {DNA}},
journal = {J.~Mol.~Bio.},
volume = 162,
number = 4,
pages = {729-73},
year = 1992
}

@article{LanderWaterman88,
author = {E.~S. Lander and M.~S. Waterman},
title = {Genomic Mapping by Fingerprinting Random Clones: A mathematical analysis},
journal = {Genomics},
volume = 2,
pages = {231-239},
year = 1988
}

@unpublished{DOE_HGP_Report97,
author = {{U. S. Dep. of Energy} and {Office of Energy Research} and {Office of Biological and Environmental Research}},
title = {Human Genome Program Report},
note = {{\tt http://www.ornl.gov/hgmis/publicat/97pr/}},
year = 1997
}

@article{HHLMRG2001,
author = {D.~H. Huson and A.~L.~Halpern and Z.~Lai and E. W.~Myers and
K. Reinert and G. G.~Sutton},
title = {Comparing assemblies using fragments and mate-pairs},
note = {WABI 2001},
journal = {LNCS},
volume = 2149,
pages = {294-306},
year = 2001
}

@unpublished{RemKraDun00,
 author = {Remington, K.~A. and Kravitz, S.~A. and Dunn, P.~J. and Halpern, A.~L. and Huson, D.~H. and Ji, R. and Lai, Z. and Lin, X.~J. and Nusskern, D.~R. and Pan, S. and Reinert, K. and Sutton, G.~G. and Zhang, Q. and Zheng, H. and Adams, M.~D. and Li, P.~W. and Myers, E.~W.},
 title = {A process for hierarchical assembly of the human genome},
 note = {Submitted to the Fourth Annual Conference on Computational
 Genomics},
 year = 2000
}

@article{Human2001short,
title = {The sequence of the human genome},
author = {J.~C. Venter and M.~D. Adams and E.~W. Myers and others},
year = 2001,
journal = {Science},
volume = 291,
pages = {1145-1434},
}


@unpublished{Human2001,
title = {The Sequence of the {Human} Genome},
author = {J. Craig Venter and M. D. Adams and E. W. Myers and P. Li and R. J.
Mural and G. G. Sutton and H. O. Smith and M. Yandell and C. A. Evans and R.
A. Holt and J. D. Gocayne and P. Amanatides and R. M. Ballew and D. H. Huson
and J. Russo Wortman and Q. Zhang and C. Kodira and X. H. Zheng and L. Chen
and M. Skupski and G. Subramanian and P. D. Thomas and J. Zhang and G. L.
Gabor Miklos and C. Nelson and S. Broder and A. G. Clark and J. Nadeau and
V. A. McKusick and N. Zinder and A. J. Levine and R. J. Roberts and M. Simon
and C. Slayman and M. Hunkapiller and R. Bolanos and A. Delcher and I. Dew
and D. Fasulo and M. Flanigan and L. Florea and A. Halpern and S.
Hannenhalli and S. Kravitz and S. Levy and C. Mobarry and K. Reinert and K.
Remington and J. Abu-Threideh and E. Beasley and K. Biddick and V. Bonazzi
and R. Brandon and M. Cargill and I. Chandramouliswaran and R. Charlab and
K. Chaturvedi and Z. Deng and V. Di Francesco and P. Dunn and K. Eilbeck and
C. Evangelista and A. E. Gabrielian and W. Gan and W. Ge and F. Gong and Z.
Gu and P. Guan and T. A. Heiman and M. E. Higgins and R-R. Ji and Z. Ke and
K. A. Ketchum and Z. Lai and Y. Lei and Z. Li and J. Li and Y. Liang and X.
Lin and F. Lu and G. V. Merkulov and N. Milshina and H. M. Moore and A. K
Naik and V. A. Narayan and B. Neelam and D. Nusskern and D. B. Rusch and S.
Salzberg and W. Shao and B. Shue and J. Sun and Z. Yuan Wang and A. Wang and
X. Wang and J. Wang and M-H. Wei and R. Wides and C. Xiao and C. Yan and A.
Yao and J. Ye and M. Zhan and W. Zhang and H. Zhang and Q. Zhao and L. Zheng
and F. Zhong and W. Zhong and S. C. Zhu and S. Zhao and D. Gilbert and S.
Baumhueter and G. Spier and C. Carter and A. Cravchik and T. Woodage and F.
Ali and H. An and A. Awe and D. Baldwin and H. Baden and M. Barnstead and I.
Barrow and K. Beeson and D. Busam and A. Carver and A. Center and M. Lai
Cheng and L. Curry and S. Danaher and L. Davenport and R. Desilets and S.
Dietz and K. Dodson and L. Doup and S. Ferriera and N. Garg and A.
Gluecksmann and B. Hart and J. Haynes and C. Haynes and C. Heiner and S.
Hladun and D. Hostin and J. Houck and T. Howland a. Chinyere Ibegwam and J.
Johnson and F. Kalush and L. Kline and S. Koduru and A. Love and F. Mann and
D. May and S. McCawley and T. McIntosh and I. McMullen and M. Moy and L. Moy
and B. Murphy and K. Nelson and C. Pfannkoch and E. Pratts and V. Puri and
H. Qureshi and M. Reardon and R. Rodriguez and Y-H. Rogers and D. Romblad
and B. Ruhfel and R. Scott and C. Sitter and M. Smallwood and E. Stewart and
R. Strong and E. Suh and R. Thomas and N. Ni Tint and S. Tse and C. Vech and
G. Wang and J. Wetter and S. Williams and M. Williams and S. Windsor and E.
Winn-Deen and K. Wolfe and J. Zaveri and K. Zaveri and J. F. Abril and R.
Guigo and M. J. Campbell and K. V. Sjolander and B. Karlak and A.
Kejariwal and H. Mi and B. Lazareva and T. Hatton and A. Narechania and K.
Diemer and A. Muruganujan and N. Guo and S. Sato and V. Bafna and S. Istrail
and R. Lippert and R. Schwartz and B. Walenz and S. Yooseph and D. Allen and
A. B. and J. Baxendale and L. Blick and M. Caminha and J. Carnes-Stine and
P. Caulk and Y-H. Chiang and M. Coyne and C. Dahlke and A. Deslattes Mays
and M. Dombroski and M. Donnelly and D. Ely and S. Esparham and C. Fosler
and H. Gire and S. Glanowski and K. Glasser and A. Glodek and M. Gorokhov
and K. Graham and B. Gropman and M. Harris and J. Heil and S. Henderson and
J. Hoover and D. Jennings and C. Jordan and J. Jordan and J. Kasha and L.
Kagan and C. Kraft and A. Levitsky and M. Lewis and X. Liu and J. Lopez and
D. Ma and W. Majoros and J. McDaniel and S. Murphy and M. Newman and T.
Nguyen and N. Nguyen and M. Nodell and S. Pan and J. Peck and W. Rowe and R.
Sanders and J. Scott and M. Simpson and T. Smith and A. Sprague and T.
Stockwell and R. Turner and E. Venter and M. Wang and M. Wen and D. Wu and
M. Wu and A. Xia and A. Zandieh and X. Zhu},
note = {In press},
year = 2001
}

@unpublished{UCSCwebsite,
author = {D.~Haussler},
title = {{Human Genome Project Working Draft}},
note = {{\tt http://genome.cse.ucsc.edu}}
}

@article{EdwardsCavalliSfroza1963,
author = {A.W.F. Edwards and L.L. Cavalli-Sfroza},
title = {The reconstruction of evolution},
journal = {Annals of Human Genetics},
volume = 27,
pages = {105-106},
year = 1963
}

@incollection{EdwardsCavalliSfroza1964,
author = {A.W.F. Edwards and L.L. Cavalli-Sfroza},
title = {Reconstruction of evolutionary trees},
booktitle = {Phenetic and Phylogenetic Classification},
editor = {V.H. Heywood and J. NcNeill},
volume = 6,
publisher = {Systematics Association},
address = {London},
pages = {67-76},
year = 1964
}
volume = 27,
pages = {105-106},
year = 1963
}

@article{EdwardsCaskey91,
author = {A. Edwards and C. T. Caskey},
title = {Closure Strategies for Random {DNA} Sequencing},
journal = {METHODS: A Companion to Methods in Enzymology},
volume = 3,
number = 1,
pages = {41-47},
year = 1991
}

@book{Bevington69,
author = {P. R. Bevington},
title = {Data Reduction and Error Analysis for the Physical Sciences},
publisher = {McGraw-Hill Inc.},
year = 1969
}

@article{AltBlumMehlhornPaul91,
 author = {Helmut Alt and Norbert Blum and Kurt Mehlhorn and Markus Paul},
 title = {Computing a Maximum Cardinality Matching of a Bipartite Graph in
 Time ${O}(n^{1.5} \sqrt{m/\log n})$},
 journal = {Inform. Process. Lett.}, 
 volume = {37},
 pages = {237--240},
 year = {1991}, 
}

@article{PapaYanna1991,
 author = {C. H. Papadimitriou and M. Yannakakis},
 title = {Optimization, approximation, and complexity classes},
 journal = {J. Comput. System Sci.},
 volume = 43,
 pages = {425--440},
 year = 1991
}
@book{SM1997,
 author = {J. Setubal and J. Meidanis},
 title = {Introduction to Computational Molecular Biology},
 publisher = {PWS},
 year = 1997
}


@book{CB2000,
 title = {Computational Molecular Biology, An Introduction},
 author = {P. Clote and R. Backofen},
 publisher = {Wiley},
 year = 2000
}

@unpublished{Web,
 author = {Web},
 note = {{http://www.isrec.isb-sib.ch/DEA/module5/T3/blast\_fasta\_uk.pdf and http://www.ncbi.nlm.nih.gov/BLAST/}}
}

@book{Pevzner2000,
 author = {P. Pevzner},
 title = {Computational Molecular Biology- an algorithmic approach},
 publisher = {MIT},
 year = 2000
}

@article{Myers1999,
 author = {E. W. Myers},
 title = {Whole-Genome {DNA} Sequencing},
 journal = {Computing in Science and Engineering, IEEE},
 month = {May-June},
 year = 1999
}

@article{Mouse16short,
 author = {R.~J. Mural and M.~D. Adams and G.~W. Myers and et al},
 title = {A comparison of whole genome shotgun-drived mouse chromosome 16
 and the human genome},
 journal = {Science},
 volume = 296,
 pages = {1661-1670},
 year = 2002
}

@article{HusonVawterWarnow99,
 author = {D.~H.~Huson and L.~Vawter and T.~J.~Warnow},
 title = {Solving large scale phylogenetic problems using {DCM}},
 journal = {Proceedings of ISMB'99},
 year = 1999
}

@inproceedings{HalpernHusonReinert2002,
 author = {A.~L.~Halpern and D.~H.~Huson and K.~Reinert},
 title = {Segment match refinement and applications},
 booktitle = {Proceedings of the ``Workshop in Algorithms in Bioinformatics''},
 note = {Springer Verlag, New York},
 pages = {12-139},
 year = 2002
}

@unpublished{Schuster2002,
 author = {Guenter Raddatz and Ramkumar Nandakkumar and Christa Lanz and
 Claudia Baar and Mark Eppinger and Andrea V"olkl and Heike Keller and
 Daniel~H.~Huson and Stephan C.~Schuster},
 title = {Comparing genomes from pathogenes and non-pathogenes:
 {{\it Wolinella succinogenes} vs. {\it Helicobacter pylori} and
 {\it Campylobacter jejuni}}},
 note = {In preparation (order of authors not final)},
 year = 2002
}

@article{Lockhart2000a,
author = {P. J. Lockhart and M. A. Steel and D. H. Huson},
title = {Invariable site models and their uses in phylogeny reconstruction.},
journal = {Syst. Biol.},
pages = {225--232},
volume = 49,
number = 2,
year = 2000
}

@article{Lockhart98,
author = {P. J. Lockhart and M. A. Steel and A. C. Barbrook and D. H. Huson
and M. A. Charleston and C. J. Howe},
title = {A covariotide model explains apparent phylogenetic
structure of oxygenic photosynthetic lineages},
journal = {Mol. Bio. Evol.},
volume = 15,
number = 9,
pages = {1183-1188},
year = 1998
}

@article{EulerDB,
author = {Pavel A. Pevzner and Haixu Tang},
title = {Fragment assembly with double-barreled data},
journal = {Bioinformatics},
volume = 17,
note = {suppl.\ 1},
pages = {S225--S233},
year = 2001
}

@article{Arachne,
author = {S. Batzoglou and D. Jaffe and K. Stanley and J. Butler and S. Gnerre
and E. Mauceli and B. Berger and J. P. Mesirov and E. S. Lander},
title = {{ARACHNE}: A Whole Genome Shotgun Assembler},
journal = {Genome Research},
volume = 12,
pages = {177-189},
year = 2002
}

@article{Ensembl,
author = {
T. Hubbard and D. Barker and E. Birney and et al.},
title = {The {Ensembl} genome database project},
journal = {Nucleic Acids Res},
volume = 30,
number = 1,
pages = {38-41},
year = 2002
}

@article{twinscan,
author = {Ian Korf and Paul Flicek and Danial Duan and Michael R. Brent},
title = {Integrating Genomic
Homology into Gene Structure Prediction},
journal = {Bioinformatics},
volume = 1,
pages = {S1-S9},
year = 2001
}

@inproceedings{BPMBL2000,
author = {Serafim Batzoglou and Lior Pachter and Jill Mesirov and Bonnie Berger
and Eric S Lander},
title = {Human and mouse gene structure: comparative analysis and application to
exon prediction},
note = {Proceedings of the Fourth International Conference on Research
in Computational Molecular Biology (RECOMB)},
year = 2000
}

@article{warnow2001,
author = {B. Moret and S. Wyman and D. Bader and T. Warnow and M. Yan},
title = {Phylogenies from Gene Order Data: A Detailed Study of Breakpoint
Analysis},
journal = {The Pacific Symposium on Biocomputing},
pages = {583-594},
year = 2001
}

@article{RokasHolland2000,
author = {Antonis Rokas and Peter W. H. Holland},
title = {Rare genomic changes as a tool for phylogenetics},
journal = {Trends in Ecology and Evolution},
volume = 15,
number = 11,
pages = {454--459},
year = 2000
}

@unpublished{Phrap94,
author = {P. Green},
title = {Documentation for {Phrap}},
note = {{\tt http://bozeman.mbt.washington.edu /phrap.docs /phrap.html}},
year = 1994
}

@inproceedings{BryantMoulton2002,
author = {D. Bryant and V. Moulton},
title = {{NeighborNet}: An Agglomerative Method for the Construction of Planar
Phylogenetic Networks},
editor = {R. Guig{\'o} and D. Gusfield},
booktitle = {Algorithms in Bioinformatics, WABI 2002},
volume = {LNCS 2452},
pages = {375-391},
year = 2002
}

@article{Puzzle,
author = {K. Strimmer and A. von Haeseler},
title = {Quartet puzzling: a quartet maximum likelihood method for
reconstructing tree topologies},
journal = MBE,
volume = 13,
pages = {964-969},
year = 1996
}

@article{MedianNetworks,
author = {H.-J. Bandelt and P. Forster and B. C. Sykes and M. B. Richards},
title = {Mitochondrial portraits of human population using median networks},
journal = {Genetics},
volume = 141,
pages = {743-753},
year = {1995}
}

@unpublished{Mesquite,
author = {W. Maddison and D. Maddison},
title = {Mesquite- a modular system for evolutionary analysis. Version 1.05},
note = {{\tt http://mesquiteproject.org}},
year = 2005
}

@article{GreedyPathMerging2002,
 author = {Daniel H. Huson and Knut Reinert and Eugene W. Myers},
 title = {The greedy path-merging algorithm for contig scaffolding},
 journal = JACM,
 volume = {49},
 number = {5},
 year = {2002},
 issn = {0004-5411},
 pages = {603--615},
 doi = {http://doi.acm.org/10.1145/585258.585260},
 publisher = {ACM Press},
 }

@unpublished{GBDP,
author = {
S. R. Henz and A. F. Auch and D. H. Huson and K. Nieselt-Struwe
and S. C. Schuster},
title = {Whole Genome-based Prokaryotic Phylogeny},
note = {Short paper in ECCB},
year = 2003
}

@unpublished{GBDP2004,
author = {
S. R. Henz and D. H. Huson and A. F. Auch and K. Nieselt-Struwe
and S. C. Schuster},
title = {Whole Genome-based Prokaryotic Phylogeny},
note = {To appear in: Bioinformatics},
year = 2003
}

@unpublished{HHAS2004,
author = {
S. R. Henz and D. H. Huson and A. F. Auch 
and S. C. Schuster},
title = {Computing the Web of Prokaryotic Life},
note = {In preparation},
year = 2004
}


@article{Holmes99,
author = {E. C. Holmes},
title = { Genomics, phylogenetics and epidemiology},
journal = {Microbiology Today},
volume = {26},
pages = {162-163},
year = 1999
}

@article{PosadaCrandall01,
author = {D. Posada and K. A. Crandall},
title = {Intraspecific gene genealogies: trees grafting into networks},
journal = {Trends in Ecology and Evolution},
volume = 16,
number = 1,
pages = {37-45},
year = 2001
}

@article{Posada2002,
author = {D. Posada},
title = {Evalutation of methods for detecting recombination from {DNA} sequences},
journal = {Molecular Biology and Evolution},
volume = 19,
number = 5,
pages = {708--717},
year = 2002
}

@unpublished{BHKN2003,
author = {D. Bryant and D. H. Huson and T. Kloepper and K. Nieselt-Struwe},
title = {Distance corrections on recombinant sequences},
note = {Proceedings of ``Workshop on Algorithms in Bioinformatics''},
year = 2003
}

@article{VBM2003,
author = {Vamsi Veeramachaneni and Piotr Bermann and Webb Miller},
title = {Aligning two fragmented sequences},
journal = DAM,
pages = {119-143},
volume = 127,
year = 2003
}

@inproceedings{Myers2001,
author = {Gene Myers},
title = {Comparing sequence scaffolds},
editor = {Thomas Lengauer and David Sankoff and Sorin Istrail and Pavel Pevzner
and Michael Waterman},
booktitle = {Proceedings of the Firfth Annual International Conference on
Computational Biology},
pages = {224,230},
year = 2001
}

@article{Dros2003short,
title = {Finishing a whole genome shotgun: Release 3 of the {\it Drosophila
melanogaster} euchromatic genome sequence},
author = {S. E. Celniker and D. A. Wheeler and B. Kronmiller and others},
journal = {Genome Biology},
year = 2002,
volume = 3,
number = 12
}
@article{Dros2003,
title = {Finishing a whole genome shotgun: Release 3 of the {\it Drosophila
melanogaster} euchromatic genome sequence},
author = {S. E. Celniker and D. A. Wheeler and B. Kronmiller and J. W. Carlson and A. Halpern and S. Patel and
M. Adams and M. Champe and S. P. Dugan and E. Frise and A. Hodgson and R. A. George and R. A. Hoskins and
T. Laverty and D. M. Muzny and C. R. Nelson and J. M. Pacleb and S. Park and B. D. Pfeiffer and S. Richards and
E. J. Sodergren and R. Svirskas and P. E. Tabor and K. Wan and M. Stapleton and G. G. Sutton and
C. Venter and G. Weinstock and S. E. Scherer and E. W. Myers and R. A. Gibbs and G. M. Rubin},
journal = {Genome Biology},
year = 2002,
volume = 3,
number = 12
}

@article{celera2003,
author = {Mark D. Adams and Granger G. Sutton and Hamilton O. Smith
and Eugene W. Myers and and J. Craig Venter},
title = {The independence of our genome assemblies},
journal = PNAS,
volume = 100,
pages = {3025-3026},
year = 2003
}

@article{Mummer2,
title = {Fast algorithms for large-scale genome alignment and comparison},
author = {A. K.~Delcher and A. Phillippy and J. Carlton and S. L. Salzberg},
journal = {Nucleic Acid Research},
volume = 30,
number = 11,
pages = {2478-2483},
year = 2002
}

@inbook{MaxCut72,
author = {R. M. Karp},
title = {Reducibility among combinatorial problems},
booktitle = {Complexity of Computer Computations},
note = {R. E. Miller and J. M. Thatcher (eds.)},
pages = {85-103},
publisher = {Plenum Press},
year = 1972
}

@unpublished{HumanEnsembl,
title = {{\tt www.ensemble.org}},
author = {Ensembl project},
note = {Joint project between EMBL - EBI and the Sanger Institute},
year = 2003
}

@article{viz2001,
author = {R. J. Turner and K. Chaturvedi and N. J. Edwards and D. Fasulo and A. L. Halpern and
D. H. Huson and O. Kohlbacher and J. R. Miller and K. Reinert and K. A. Remington and
R. Schwartz and B. Walenz and S. Yooseph and Sorin Istrail},
title = {Visualization Challenges for a New Cyberpharmaceutical Computing
Paradigm},
note = {Invited contribution},
journal = {2001 Symposium on Parallel and Large-Data Visualization and Graphics},
pages = {7-18},
year = 2001
}

@article{lin99wholegenomeOpticalMapping,
 author = {Jieyi Lin and Rong Qi and Christopher Aston and Junping Jing and 
 Thomas S. Anantharaman and Bud Mishra and Owen White and Michael J. Daly and 
 Kenneth W. Minton and J. Craig Venter and David C. Schwartz},
 title = {Whole-Genome Shotgun Optical Mapping of Deinococcus radiodurans},
 journal = {Science},
 year = {1999},
 volume = {285},
 pages = {1558--1562}
}

@article{ensembl2002,
author = {Hubbard, T. and Barker, D. and Birney, E. and Cameron, G. and Chen, Y. and Clark, L. and Cox, T. and Cuff, J. and Curwen, V. and Down, T. and Durbin, R. and Eyras, E. and Gilbert, J. and Hammond, M. and Huminiecki, L. and Kasprzyk, A. and Lehvaslaiho, H. and Lijnzaad, P. and Melsopp, C. and Mongin, E. and Pettett, R. and Pocock, M. and Potter, S. and Rust, A. and Schmidt, E. and Searle, S. and Slater, G. and Smith, J. and Spooner, W. and Stabenau, A. and Stalker, J. and Stupka, E. and Ureta-Vidal, A. and Vastrik, I. and Clamp, M.},
title = {{The Ensembl genome database project}},
journal = {Nucl. Acids. Res.},
volume = {30},
number = {1},
pages = {38-41},
year = {2002},
abstract = {The Ensembl (http://www.ensembl.org/) database project provides a bioinformatics framework to organise biology around the sequences of large genomes. It is a comprehensive source of stable automatic annotation of the human genome sequence, with confirmed gene predictions that have been integrated with external data sources, and is available as either an interactive web site or as flat files. It is also an open source software engineering project to develop a portable system able to handle very large genomes and associated requirements from sequence analysis to data storage and visualisation. The Ensembl site is one of the leading sources of human genome sequence annotation and provided much of the analysis for publication by the international human genome project of the draft genome. The Ensembl system is being installed around the world in both companies and academic sites on machines ranging from supercomputers to laptops.
},
URL = {http://nar.oupjournals.org/cgi/content/abstract/30/1/38},
eprint = {http://nar.oupjournals.org/cgi/reprint/30/1/38.pdf}
}

@unpublished{HHLDR2003,
author = {A. L. Halpern and D. H. Huson and R. Lippert
and O. Delgado-Friedrichs},
title = {Layout Problems in Assembly Comparison},
note = {Submitted},
year = 2003
}

@book{compgeom2000,
author = {M. de Berg and M. van Kreveld and M. Overmars and O. Schwarzkopf},
title = {Computational Geometry --- Algorithms and Applications},
edition = {2nd},
publisher = {Springer},
year = {2000}
}


@unpublished{jsplits,
author = {D. H. Huson and D. Bryant},
title = {Application of Phylogenetic Networks in Evolutionary Studies},
note = {To appear in: Molecular Biology and Evolution, software available from
{\tt www.splitstree.org}},
year = 2005
}

@article{rnadatabase,
author = {J. R. Cole and B. Chai and T. L. Marsh and R. J. Farris and Q. Wang
and S. A. Kulam and S. Chandra and D. M. McGarrell and T. M. Schmidt
and G. M. Garrity and J. M. Tiedje},
title = {The Ribosomal Database Project {(RDP-II)}: previewing a new autoaligner
that allows regular updates and the new prokaryotic taxonomy},
journal = {Nucleic Acids Res},
year = 2003,
volume = 31,
number = 1,
pages = {442-3}
}

@incollection{HollandMoulton2003,
author = {B. Holland and V. Moulton},
title = {Consensus networks: A method for visualizing incompatibilities in
collections of trees},
booktitle = {Proceedings of ``Workshop on Algorithms in Bioinformatics''},
series = {LNBI},
volume = 2812,
publisher = {Springer},
editor = {G. Benson and R. Page},
pages = {165--176},
year = 2003
}

@article{graphmatching,
author = {H. N. Gabow},
title = {An efficient implementation of Edmonds' algorithm for maximum matching
on graphs},
journal = JACM,
volume = {23},
pages = {221--234},
year = 1976
}


@article{woese1987,
 author = {C.~R. Woese},
 title = {Bacterial Evolution},
 journal = {Microbiol. Rev.},
 volume = {51},
 pages = {221-272}, 
 year = {1987}
}

@article{bork1998,
 author = {M.~A. Huynen and P. Bork},
 title = {Measuring genome evolution},
 journal = {Proc.~Natl.~Acad.~Sci.~USA},
 pages = {5849-5856},
 volume = {95},
 year = {1998}
}

@article{bork1999,
 author = {B. Snel and P. Bork and M.~A. Huynen},
 title = {Genome phylogeny based on gene content},
 journal = {Nature},
 year = {1999},
 pages = {108-110},
 volume = {21}
} 

@article{olsen1994,
 author = {G.~J. Olsen and C.~R. Woese and R. Overbeek},
 title = {The winds of (evolutionary) change: breathing new life into microbiology},
 journal = {J.~Bact.},
 volume = {176},
 year = {1994},
 pages = {1-6}
} 

@article{upgma_sokal1958,
 author = {R.~R. Sokal and C.~D. Michener},
 title = {A statistical method for evaluating systematic relationships},
 journal = {University of Kansas Scientific Bulletin}, 
 year = {1958},
 OPTkey = {},
 volume = {28},
 pages = {1409-1438},
 OPTnote = {},
 OPTannote = {}
}

@article{studier_kepler1988,
 author = {J.~A. Studier and K.~J. Keppler},
 title = {A note on the neighbour-joining algorithm of
 {Saitou and Nei}},
 journal = {Mol.~Biol.~Evol.},
 year = {1988},
 OPTkey = {},
 volume = {5},
 pages = {729-731},
 OPTnote = {},
 OPTannote = {}
}

@article{hacker2001,
 author = {J.~Hacker and E.~Carnier},
 title = {Ecological fitness, genomic islands and bacterial pathogenicity},
 journal = {EMBO Reports},
 year = {2001},
 pages = {376-381},
 volume = {2}
}

@inproceedings{sankhoff_blanchette1997,
 author = {D. Sankhoff and M. Blanchette},
 editor = {T. Jiang and D.~T. Lee},
 title = {The median problem for breakpoints in comparative genomics},
 booktitle = {Computing and Combinatorics,
 Proc. COCOON'97. Lecture Notes in Computer Science},
 year = {1997},
 note = {Springer Verlag, New York},
 volume = {1276}
}

@article{sankhoff_bryant2000,
 author = {D. Sankhoff and D. Bryant and M. Denault and B.~F. Lang and G. Burger},
 title = {Early Eukaryote Evolution Based on Mitochondrial gene order Breakpoints},
 journal = {J.~Comp.~Biol.},
 year = {2000},
 volume = {7},
 pages = {521-535},
}

@misc{ncbi_taxonomy,
author = {NCBI},
title = {Microbial Complete Genomes Taxonomy},
howpublished = {http://www.ncbi.nlm.nih.gov/PMGifs/Genomes/new\_micr.html},
year = 2003
}

@misc{ebi_taxonomy,
author = {EBI},
title = {Completed Genomes Bacteria},
howpublished = {http://www.ebi.ac.uk/cgi-bin/genomes/genomes.cgi?genomes = Bacteria},
year = {2003}
}

@article{moran_mira2001,
author = {N.~A. Moran and A.~Mira},
title = { The process of genome shrinkage in the obligate symbiont Buchnera aphidicola.},
journal = {Genome Biol.},
volume = {2},
pages = {1-12},
year = {2001}
}

@article{andersson1998,
 author = {S.~G.~E. Andersson and A. Zomorodipour and
 J.~O. Andersson and T. Sicheritz-Ponten
 and C.~M.~U. Alsmark and R.~M. Podwoski and
 A.~K. N\"aslund and A.-C. Eriksson and
 H.~H. Winkler and C.~G. Kurland}, 
 title = {The genome sequence of Rickettsia
 prowazekii and the origin of mitochondria},
 journal = {Nature},
 volume = {396},
 pages = {133-140},
 year = {1998}
} 

@article{andersson2000,
 author = {I. Tamas and L. Klasson and B. Canb\"ack and
 A.~K. N\"aslund and A.-E. Eriksson and J.~J. Wernegren
 and J.~P. Sandstr\"om and N.~A. Moran
 and S.~G.~E. Andersson},
 title = {50 million years of genomic stasis in endosymbiotic bacteria},
 journal = {Science},
 volume = {296},
 pages = {2376-2379},
 year = {2000}
}

@article{sober_steel2002,
 author = {E. Sober and M. Steel},
 title = { Testing the Hypothesis of Common Ancestry},
 volume = {218},
 journal = {J.~theor.~Biol.},
 year = {2002},
 pages = {395-408}
}

@incollection{woese2000,
 author = {C.~R. Woese},
 title = "{Prokaryote Systematics: The Evolution of a Science}",
 booktitle = {The Prokaryotes},
 volume = {3},
 editor = {A. Balows and H. G. Tr\"uper and M. Dworkin and W. Harder and K. H.
 Schleifer},
 publisher = {Springer Verlag, New York},
 year = {2000} 
}

@article{parkhill2000,
author = {J. Parkhill and M. Achtman and K.~D. James and S.~D. Bentley and C. Churcher and
 S.~R. Klee and G. Morelli and D. Basham and D. Brown and T. Chillingworth and
 R.~M. Davies and P. Davis and K. Devlin and T. Feltwell and N. Hamlin and S. Holyrod and
 K. Jagels and S. Leather and S. Moule and K. Mungali and M.~A. Quail and
 M.-A. Rajandream and K.~M. Rutherford and M. Simmonds and J. Skelton and
 S. Whitehead and B.~G. Spratt and B. G. Barrell}, 
 title = "{Complete {DNA} sequence of a serogroup A strain of {\it Neisseria meningitidis} Z2491}",
 journal = {Nature},
 year = {2000},
 pages = {502-506},
 volume = {404}
} 

@misc{warnow2003,
 howpublished = {http://www.smi.stanford.edu/projects/helix/psb02/wang.pdf},
 author = {L.~S. Wang and R.~K. Jansen and B.~M.~E. Moret and
 L. A. Raubeson and T. Warnow},
 title = "{Fast Phylogenetic Methods for the Analysis of Genome Rearrangement Data: An Empirical Study}",
 year = {2003}
}

@article{Wolinella,
author = {C. Baar and M. Eppinger and G. Raddatz and J. Simon and C. Lanz and
O. Klimmek and R. Nadakumar and R. Gross and A. Rosinus and H. Keller and P.
Jagtap and B. Linke and F. Meyer and H. LEderer and S. C. Schuster},
title = {Complete genome sequence and analysis of {\it Wolinella
succinogenes}},
journal = PNAS,
volume = 100,
number = 20,
pages = {11690--11695},
year = 2003
}

@article{Koonin2001,
author = {Y. I. Wolf and I. B. Rogozin and N. V. Grishin and R. L. Tatusov and
E. V. Koonin},
title = {Genome trees constructed using five different approaches suggest new
major bacterial clades},
journal = {BMC Evolutionary Biology},
volume = {1:8},
year = 2001
}

@article{Koonin2002,
author = {Y. I. Wolf and I. B. Rogozin and N. V. Grishin and E. V. Koonin},
title = {Genome trees and the {Tree of Life}},
journal = {TRENDS in Genetics},
volume = {18},
number = 9,
pages = {472--479},
year = 2002
}

@article{Koonin2003,
author = {B. G. Mirkin and T. I. Fenner and M. Y. Galperin and
E. V. Koonin},
title = {Algorithms for computing parsimonious evolutionary scenarios for
genome evolution, the last universal common ancestor and domiance of
horizontal gene transfer in the evolution of prokaryotes},
journal = {BMC Evolutionary Biology},
volume = {3:2},
year = 2003
}

@article{KarevKoonin2003,
author = {G. P. Karev and Y. I. Wolf and E. V. Koonin},
title = {Simple stochastic birth and death models of genome evolution: was
there enough time for us to evolve?},
journal = {Bioinformatics},
volume = 19,
number = 15,
pages = {1889--1900},
year = 2003
}

@unpublished{HusonSteel2003a,
author = {D. H. Huson and M. Steel},
title = {Distances that perfectly mislead},
note = {Submitted},
year = 2003
}

@article{HusonSteel2003b,
author = {D. H. Huson and M. Steel},
title = {Phylogenetic Trees Based on Gene Content},
jorunal = {Bioinformatics},
pages = {2044-9},
volume = 20,
number = 13,
year = 2004
}

@article{debry,
author = {R. W. DeBry and N. A. Slade},
title = {Cladistic analysis of restriction endonuclease cleavage map data
within a maximum likelihood framework},
journal = {Systematic Zoology},
volume = {31},
pages = {21-34},
year = 1985
}

@book{Feller50,
author = {W. Feller},
title = {An introduction to probability theory and its applications},
volume = 1,
edition = {2nd},
publisher = {John Wiley and Sons, Inc.},
address = {New York},
year = 1950
}

@article{LeQuense74,
author = {W. J. {Le Quesne}},
title = {The uniquely evolved character and its cladistic application},
journal = {Systematic Zoology},
volume = {23},
pages = {513-517},
year = {1974}
}

@article{Kunin2003,
author = {V. Kunin and C. A. Ouzounis},
title = {{GenTRACE}- reconstruction of gene content of ancestral species},
journal = {Bioinformatics},
volume = {19},
number = 11,
pages = {1412-1416},
year = {2003}
}

@book{SempleSteel2003,
author = {C. Semple and M. A. Steel},
publisher = {Oxford University Press},
title = {Phylogenetics},
year = {2003},
}

@article{SankoffNadeau96,
author = {D. Sankoff and J. H. Nadeau},
title = { Conserved synteny as a measure of genomic distance},
journal = {Discr. Appl. Math.},
volume = {71},
pages = {247-257},
year = {1996}
}

@article{FitzGibbonHouse1999,
author = {S. T. Fitz-Gibbon and C. H. House},
title = {Whole gnome-based phylogenetic analysis of free-living
microorganisms},
journal = {Nucleic Acis Research},
volume = {27},
number = 21,
pages = {4218--4222},
year = {1999}
}


@article{SpeedyGreedy,
author = {H. J. Bandelt and V. Macaulay V and M. Richards},
title = {Median networks: speedy construction and greedy reduction, one
simulation, and two case studies from human mtDNA},
journal = {Mol. Phylogenet. Evol.},
year = 2000,
volume = 16,
number = 1,
pages = {8-28}
}
 
@book{Felsenstein2004,
author = {J. Felsenstein},
title = {Inferring Phylogenies},
year = 2004,
publisher = {Sinauer Associates, Inc.}
}

@article{spectronet,
author = {K. T. Huber and M. Langton and D. Penny and V. Moulton and M. Hendy},
title = {Spectronet: A package for computing spectra and median networks},
journal = {Applied Bioinformatics},
volume = 1,
year = 2002,
pages = {159-161}
}

@article{HGTcritical,
author = {C. G. Kurland and B. Canback and O. G. Berg},
title = {Horizontal gene transfer: A
critical view},
journal = {PNAS},
volume = 100,
number = 17,
pages = {9658-9662},
year = 2003
}

@incollection{mea83,
author = {C. A. Meacham},
title = {Theoretical and computational considerations of the compatibility of
qualitative taxonomic characters},
editor = {J. Felsenstein},
booktitle = {Numerical Taxonomy},
volume = {G1},
series = {NATO ASI Series},
publisher = {Springer},
address = {Berlin},
year = 1983
}

@article{leastsquares,
author = {R. C. Winkworth and D. Bryant and P. Lockhart and D. Havell
and V. Moulton},
title = {
Biogeographic interpretation of splits graphs: least squares optimization of
branch lengths},
journal = {Systematic Biology},
note = {Submitted},
year = 2004
}

@article{DressHuson2004,
author = {A. W. M. Dress and D. H. Huson},
title = {Constructing Splits Graphs},
journal = {IEEE/ACM Transactions in Computational Biology and Bioinformatics},
pages = {109-115},
volume = 1,
number = 3,
year = 2004
}

@incollection{HalperinKarp2004,
author = {E. Halperin and R. M. Karp},
title = {Perfect Phylogeny and Haplotype Assignment},
booktitle = {Proceedings of the Eighth Annual Internation Conference on
Research in Computational Molecular Biology},
publisher = {ACM Press},
pages = {10--19},
year = 2004
}

@inproceedings{DezulianSteel2004,
author = {T. Dezulian and M. A. Steel},
title = {Phylogenetic closure operations and homoplasy-free evolution},
booktitle = {Proceedings of the meeting of the International Federation 
of Classification Societies (IFCS) 2004, ed. D. Banks, L. House, 
F. R. McMorris, P. Arabie, and W. Gaul},
publisher = {Springer-Verlag, Berlin},
pages = {395--416},
year = 2004
}

@article{pryor00,
author = {B. M. Pryor and R. L. Gilbertson},
title = {{
Phylogenetic relationships among Alternaria and related fungi
based upon analysis of nuclear internal transcribed sequences
and mitochondrial small subunit ribosomal {DNA} sequences}},
journal = {Mycological Research},
volume = {104},
number = {11},
pages = {1312--1321},
year = 2000
}

@article{pryor03,
author = {B. M. Pryor and D. M. Bigelow},
title = {{
Molecular characterization of Embellisia and Nimbya species
and their relationship to Alternaria, Ulocladium and Stemphylium}},
journal = {Mycologia},
volume = {95},
number = {6},
pages = {1141-1154},
year = 2003
}

@article{Sanderson94,
author = {M. J. Sanderson and M. J. Donoghue and W. Piel and T. Eriksson},
title = {TreeBASE: a prototype database of phylogenetic analyses
and an interactive tool for browsing the phylogeny of life},
journal = {Amer. Jour. Bot.},
volume = {81},
number = {6},
pages = {183},
year = 1994
}


@article{Schuster2004a,
author = {S. Rendulic and P. Jagtap and A. Rosinus and M. Eppinger and C. Baar
and C. Lanz and H. Keller and C. Lambert and K. J. Evans and R. Till and
A. Goesmann and F. Meyer and R. E. Sockett and S. C. Schuster},
title = {A Predator unmasked: The life cycle of
{{\it Bdellovibrio bacteriovorus}}
from a genomic perspective},
journal = {Science},
volume = 303,
pages = {689-692},
year = 2004
}

@unpublished{Schuster2004b,
author = {S. Rendulic and M. Eppinger and C. Baar and G. Raddatz and P. Jagtap
and A. Rosinus and C. Lanz and H. Keller and A. Thiel and G. Velicer
and P. Schmidt and S. C. Schuster},
title = {Comparative and Functional Genomic Studies on Prey-Dependent and
Prey-Independent Strains of {{\it Bdellovibrio bacteriovorus}}},
note = {In Preparation},
year = 2004
}

@book{Berge1976,
author = {Claude Berge},
title = {Graphs and hypergraphs},
publisher = {North Holland},
year = 1976
}

@article{CGViz,
author = {O. Delgado~Friedrichs and T. Dezulian and D. H. Huson},
title = {A meta-viewer for biomolecular data},
journal = {GI Jahrestagung},
volume = 1,
pages = {375--380},
year = 2003
}

@article{REPuter,
author = {
S. Kurt and J. V. Choudhuri and E. Ohlebusch and C. Schleiermacher and J.
Stoye and R. Giegerich},
title = {{REPuter}: The Manifold Applications of Repeat Analysis on a Genomic
Scale},
journal = {Nucleic Acids Res.},
volume = 29,
number = 22,
pages = {4633-4642},
year = 2001
}

@article{Kellis2003,
author = {M. Kellis and N. Patterson and Ma. Endrizzi and E. S. Lander},
title = {Sequencing and comparison of yeast species to identify genes and
regulatory elements},
journal = {Nature},
volume = 423,
pages = {241-254},
year = 2003
}

@inproceedings{SempleSteelClosure2001,
author = {C. Semple and M. A. Steel},
title = {Tree recontruction via a closure operation on partial splits},
booktitle = {Computational Biology (proceedings of JOBIM 2000), LNCS 2066},
publisher = {Springer-Verlag},
year = 2001
}

@article{GlobalAlign,
author = {S. B. Needleman and C. D. Wunsch},
title = {A general method applicable to the search for similarities in the amino acid sequences of two proteins},
journal = {JMB},
volume = 48,
pages = {443-453},
year = 1970
}

@article{LocalAlign,
author = {T. F. Smith and M. S. Waterman},
title = {Identification of common molecular subsequences},
journal = {JMB},
volume = 147,
pages = {195-197},
year = 1981
}

@unpublished{schuster2004,
title = {The power and Limitations of Genome Comparison:
A Study of $\epsilon$-Proteobacteria},
author = {
M. Eppinger and C. Baar and G. Raddatz and D. H. Huson and
S. C. Schuster},
journal = {Nature Reviews Microbiology},
note = {submitted},
year = 2004
}

@article{zclosure,
author = {D. H. Huson and T. Dezulian and T. Kloepper and M. A. Steel},
title = {Phylogenetic Super-Networks from Partial Trees},
journal = {IEEE/ACM Transactions in Computational Biology and Bioinformatics},
volume = 1,
number = 4,
pages = {151-158},
year = 2004
}

@inproceedings{Nakhleh2004,
author = {L. Nakhleh and T. Warnow and C. R. Linder},
title = {Reconstructing reticulate evolution in species - theory and
practice},
booktitle = {Proceedings of the Eight International Conference on Research
in Computational Molecular Biology (RECOMB)},
pages = {337-346},
year = 2004
}

@inproceedings{Gusfield2003,
author = {D. Gusfield and S. Eddhu and C. Langley},
title = {Efficient reconstruction of phylgenetic networks with constrained
recombination},
booktitle = {Proceedings of the 2003 IEEE CSB Bioinformatics Conference},
year = 2003
}

@unpublished{Gusfield2004,
author = {D. Gusfield, S. Eddhu and C. Langley},
title = {The Fine Structure of Galls in Phylogenetic Networks},
note = {to appear in: INFORMS J. of Computing Special Issue on Computational Biology},
year = 2004
}

@article{buttercups2001,
author = {P. J. Lockhart and P. A. McLenachan and D. Havell and D. Glenny 
and D. H. Huson and U. Jensen},
title = {Phylogeny, dispersal and radiation of {New Zealand} alpine buttercups:
molecular evidence under split decomposition},
journal = {Ann Missouri Bot Gard},
volume = 88,
pages = {458-477},
year = 2001,
}

@article{Wang2001,
author = {L. Wang and K. Zhang and L. Zhang},
title = {Perfect Phylogenetic Networks with Recombination},
journal = {Journal of Computational Biology},
volume = 8,
number = 1,
pages = {69-78},
year = 2001
}

@article{Doolittle1999,
author = {W. F. Doolittle},
title = {Phylogenetic Classification and the Universal Tree},
journal = {Science},
volume = 284,
pages = {2124-2128},
year = 1999,
}

@book{azum,
author = {N. Alon and J. H. Spencer},
title = {The Probabilistic Method},
edition = {2nd},
publisher = {John Wiley},
year = 2000
}

@article{Tajima83,
author = {F. Tajima},
title = {Evolutionary relationships of {DNA} sequences in finite
populations},
journal = {Genetics},
volume = 105,
pages = {437--460},
year = 1983
}

@article{GPWG2001,
author = {Grass Phylogeny Working Group},
title = {Phylogeny and Subfamilial Classification of the Grasses (Poaceae)},
journal = {Annals of the Missouri Botanical Garden},
volume = 88,
number = 3,
pages = {373-457},
year = 2001,
}

@proceedings{sung2004,
authors = {J. Jansson and W.-K. Sung},
title = {Inferring a Level--1 Phylogenetic Network from a Dense Set of Rooted
Triplets},
journal = {Proceedings of the Tenth International Computing and Combinatorics
Conference (COCOON 2004)},
series = {LNCS},
volume = 3106,
publisher = {Springer--Verlag},
year = 2004
}

@article{Maddison97,
author = {W. P. Maddison},
title = {Gene trees in species trees},
journal = {Syst. Biol.},
volume = 46,
number = 3,
pages = {523-536},
year = 1997
}

@article{stepeloc93,
author = {M. A. Steel and P. Lockhart and D. Penny},
title = {Confidence in evolutionary trees from biological sequence data},
journal = {Nature},
volume = 364,
pages = {440-442},
year = 1993
}

@article{Bafna2004,
author = {V. Bafna and V. Bansal},
title = {The Number of recombination events in a sample history: conflict
graph and lower bounds},
journal = {IEEE/ACM Transactions in Computational Biology and Bioinformatics},
pages = {78-90},
volume = 1,
number = 2,
year = 2004
}

@article{Hein1990,
author = {J. Hein},
title = {Reconstructing evolution of sequences subject to recombination using
parsimony},
journal = {Math. Biosci.},
pages = {185--200},
year = 1990
}

@article{Sang2000,
author = {T. Sang and Y. Zhong},
title = {Testing hybrization hypotheses based on incongruent gene trees},
journal = {System. Biol.},
volume = 49,
number = 3,
pages = {422-424},
year = 2000
}

@article{GriffithsMarjoram1996,
author = {R. C. Griffiths and P. Marjoram},
title = {Ancestral Inference from Samples of {DNA} Sequences with Recombination},
journal = {J. Computational Biology},
volume = 3,
pages = {479-502},
year = 1996
}

@article{MyersGriffiths2003,
author = {S. R. Myers and R. C. Griffiths},
title = {Bounds on the minimal number of recombination events in a sample
history},
journal = {Genetics},
volume = 163,
pages = {375--394},
year = 2003
}

@article{Hein1993,
author = {J. Hein},
title = {A Heuristic Method to Reconstruct the History of Sequences Subject to Recombination},
journal = {J. Mol. Evol.},
volume = 36,
pages = {396-405},
year = 1993,
}

@article{Makarenkov2000,
author = {V. Makarenkov and P. Legendre},
title = {From a phylogenetic tree to a reticulated network},
journal = {J. Comput. Biol.},
volume = 11,
number = 1,
pages = {195-212},
year = 2000,
}

@article{Makarenkov2004,
author = {V. Makarenkov, P. Legendre and Y. Desdevises},
title = {Modelling phylogenetic relationships using reticulated networks},
journal = {Zoologica Scripta},
volume = 33,
pages = {88-96},
year = 2004,
}

@article{Hudson83,
author = {R. R. Hudson},
title = {Properties of the Neutral Allele Model with intergenic Recombination},
journal = {Theoretical Population Biology},
volume = 23,
pages = {183--201},
year = 1983
}

@article{HudsonKaplan85,
author = {R. R. Hudson and N. L. Kaplan},
title = {Statistical properties of the number of recombination events in the
history of a sample of {DNA} sequences},
journal = {Genetics},
volume = 111,
pages = {147--164},
year = 1985
}

@inproceedings{Gusfield2005,
author = {D. Gusfield and V. Bansal},
title = {A Fundamental Decomposition Theory for Phylogenetic Networks and
Incompatible Characters},
booktitle = {Proceedings of the Ninth International Conference on
Research in Computational
Molecular Biology (RECOMB)},
year = 2005
}

@article{Kreitman85,
author = {M. Kreitman},
title = {Nucleotide polymorphism at the alcohol dehydrogenase locus of
{Drosophila melanogaster}},
journal = {Genetics},
volume = 11,
pages = {147--164},
year = 1985
}

@article{Holland2004,
author = {B. Holland and K. Huber and V. Moulton and P. J. Lockhart},
title = {Using consensus networks to visualize contradictory evidence for
species phylogeny},
journal = {Molecular Biology and Evolution},
volume = 21,
pages = {1459--1461},
year = 2004
}

@article{Rieseberg2003,
author = {L. H. Rieseberg and O. Raymond and D. M. Rosenthal and Z. Lai and
K. Livingstone and T. Nakazato and J. L. Durphy and A. E. Schwarzbach and
L. A. Donovan and C. Lexer},
title = {Major ecological transitions in annual sunflowers facilitated by
hybridization},
journal = {Science},
volume = 301,
pages = {1211-1216},
year = 2003
}

@article{BaroniSempleSteel2004,
author = {M. Baroni and C. Semple and M. A. Steel},
title = {A framework for representing reticulate evolution},
journal = {Annals of Combinatorics},
year = {In press}
}

@article{HHML2004,
author = {B. Holland and K. Huber and V. Moulton and P. J. Lockhart},
title = {Using consensus networks to visualize contradictory evidence for species
phylogeny},
journal = {Molecular Biology and Evolution},
volume = 21,
pages = {1459--1461},
year = 2004
}

@article{Rosenberg2002,
author = {N. A. Rosenberg},
title = {The probability of topological concordance of gene trees and
species trees},
journal = {Theor. Pop. Biol.},
volume = 61,
pages = {225--247},
year = 2002
}

@article{PAL,
author = {A. Drummond and K. Strimmer},
title = {{PAL}: An object-oriented programming libary for molecular evolution and phylogenetics},
journal = {Bioinformatics},
volume = 17,
pages = {662-663},
year = 2001
}

@article{MrBayes,
author = {J.P. Huelsenbeck and F. Ronquist},
title = {{MRBAYES}: {Bayesian} inference of phylogenetic trees},
journal = {Bioinformatics},
volume = 17,
number = 8,
pages = {754-755},
year = 2001
}

@inproceedings{Reticulate2005,
author = {D.H. Huson and T. Kloepper and P.J. Lockhart and M.A. Steel},
title = {Reconstruction of Reticulate Networks from Gene Trees},
booktitle = {Proceedings of the Ninth International Conference on
Research in Computational Molecular Biology (RECOMB)},
year = 2005
}

@article{Baysian2001,
author = {J.P. Huelsenbeck and F. Ronquist and R. Nielsen and J.P. Bollback},
title = {Bayesian inference of phylogeny and its impact on evolutionary
biology},
journal = {Science},
volume = 294,
pages = {2310-2314},
year = 2001
}

@article{Parfitt1997,
author = {D.E. Parfitt and M.L. Badenes},
title = {Phylogeny of the genus {\it Pistacia} as determined from analysis of the chloroplast genome},
journal = {PNAS},
volume = 94,
pages = {7987--7992},
year = 1997
}

@article{Kumar1998,
author = {A. Kumar and W.C. Black and K.S. Rai},
title = {An estimate of phylogenetic relationships among culicine mosquitoes
using a restriction map of the {rDNA} cistron},
journal = {Insect Molecular Biology},
volume = 7,
number = 4,
pages = {367-373},
year = 1998
}

@unpublished{LMNW2004,
author = {C.R. Linder and B.M.E. Moret and L. Nakhleh and T. Warnow},
title = {Network (Reticulate) Evolution: Biology, Models, and Algorithms},
note = {A tutorial presented at the Ninth Pacific Symposium on Biocomputing},
year = 2004
}

@unpublished{SongHein2003,
author = {Y.S. Song and J. Hein},
title = {Parsimonious Reconstruction of Sequence Evolution and Haplotype
Blocks: Finding the Minimum Number of Recombination Events},
note = {Proceedings of the Workshop on Algorithms in Bioinformatics},
pages = {287-302},
year = 2003
}

@article{SongHein2004,
author = {Y.S. Song and J. Hein},
title = {On the minimum Number of Recombination Events in the Evolutionary
History of {DNA} Sequences},
journal = {J. Math. Biol.},
volume = 48,
pages = {160-186},
year = 2004
}

@article{SongHein2005,
author = {Y.S. Song and J. Hein},
title = {Constructing Minimal Ancestral Recombination Graphs},
journal = {J. Comp. Biol.},
volume = 12,
pages = {147-169},
year = 2005
}

@article{NetView2003,
author = {K. Kryukov and N. Saitou},
title = {Netview: Application Software for Constructing and Visually Exploring
Phylogenetic Networks},
journal = {Genome Informatics},
volume = 14,
pages = {280-281},
year = 2003
}

@article{TRex2001,
author = {V. Makarenkov},
title = {{T-REX}: Reconstructing and visualizing phylogenetic trees and
reticulation networks},
journal = {Bioinformatics},
volume = 17,
number = 7,
pages = {664-668},
year = 2001
}

@article{Worobrey2001,
author = {M. Worobey},
title = {A novel approach to detecting and measuring recombination:
new insights into evolution in viruses, bacteria and mitochondria},
journal = {Mol. Biol. Evol.},
volume = 18,
pages = {1425--1434},
year = 2001
}
@article{Bootscanning1995,
author = {M. Salminen and J.K. Carr and D.S. Burke and F.E. McCutchan},
title = {Identification of breakpoints in intergenotypic recombinants of
{HIV} type 1 by bootscanning},
journal = {AIDS Res. Hum. Retroviruses},
volume = 11,
pages = {1423--1425},
year = 2001
}

@article{VisRD,
title = {{VisRD} - Visual Recombination Detection},
author = {K. Forslund and D.H. Huson and V. Moulton},
journal = {Bioinformatics},
volume = 20,
number = 18,
pages = {3654-3655},
year = 2004
}

@inproceedings{HallettLagergrenTofigh2004,
author = {M. Hallett and J. Largergren and A. Tofigh},
title = {Simultaneous Identification of Duplications and Lateral Transfers},
booktitle = {Proceedings of the Eight International Conference on Research in
Computational Molecular Biology (RECOMB)},
pages = {347-356},
year = 2004
}

@inproceedings{HallettLagergren2000,
author = {M. Hallett and J. Largergren},
title = {New Algorithms for the Duplication-Loss Model},
booktitle = {Proceedings of the Fourth International Conference on Research
in Computational Molecular Biology (RECOMB)},
pages = {138-146},
year = 2000
}

@unpublished{Tutorial2005,
author = {D.H. Huson},
title = {Introduction to Phylogenetic Networks},
note = {Tutorial presented at ISMB},
year = 2005
}

@article{SchierupHein2001,
author = {M.H. Schierup and J. Hein},
title = {Consequences of recombination on traditional phylogenetic analysis},
journal = {Genetics},
volume = 156,
pages = {879-891},
year = 2000
}

@article{Zink1991,
author = {R. M. Zink and D. L. Dittmann and W. L. Roots},
title = {Mitochondrial {DNA} variation and the phylogeny of Zonotrichia},
title = {Mitochondrial DNA variation and the phylogeny of Zonotrichia},
journal = {The Auk},
volume = 108,
number = 3,
pages = {578-584},
year = 1991
}

@article{NEXUS,
author = {D.R. Maddison and D.L. Swofford and W.P. Maddison},
title = {{NEXUS}: an extendible file format for systematic information},
journal = {System. Bio.},
volume = 46,
number = 4,
pages = {590-621},
year = 1997
}

@article{Kimura81,
author = {M. Kimura},
title = {Estimation of evolutionary distances between homologous
nucleotide sequences},
journal = {PNAS},
volume = 78,
pages = {454-458},
year = 1981
}

@book{SimulatedAnnealing,
author = {P.J.M. Van Laarhoven and E.H.L. Aarts},
title = {Simulated annealing: theory and applications},
year = 1987
}

@article{GreatDeluge,
author = {G. Dueck and T. Scheuer},
title = {Threshold Accepting: A General Purpose Optimization Algorithm Appearing
Superior to Simulated Annealing},
journal = {Journal of Computational Physics},
volume = 90,
number = 1, pages = {161-175},
year = 1990
}

@article{HendyPenny93,
author = {M.D. Hendy and D. Penny},
title = {Spectral Analysis of Phylogentic Data},
journal = {Journal of Classification},
volume = 10,
pages = {5--24},
year = 1993
}

@article{TCS,
author = {M. Clement and D. Posada and K.A. Crandall},
title = {{TCS}: a computer program to estimate gene genealogies},
journal = {Molecular Ecology},
volume = 9,
pages = {1657-1659},
year = 2000
}

@article{Templeton1992,
author = {A.R. Templeton and K.A. Crandall and C.F. Sing},
title = {A cladistic analysis of phenotypic associations with haplotypes
inferred from restriction endonuclease mapping and {DNA} sequence data. {III.}
{Cladogram} estimation.},
journal = {Genetics},
volume = 132,
pages = {619-633},
year = 1992
}

@article{Fitch1997,
author = {W. Fitch},
title = {Networks and viral evolution},
journal = {J. Mol. Evol.},
volume = 44,
pages = {S65--S75},
}

@article{LegendreMakarenkov2002,
author = {P. Legendre and V. Makarenkov},
title = {Reconstruction of biogeographic and evolutionary networks using
reticulograms},
journal = {Systematic Biology},
volume = 51,
number = 2,
pages = {199-216},
year = 2002
}

@article{Muscle,
author = {R.C. Edgar},
title = {{MUSCLE}: multiple sequence alignment with high accuracy and high
throughput},
journal = {Nucleic Acids Research},
volume = 32,
number = 5,
pages = {1792-97},
year = 2004
}

@article{ClustalW,
author = {J.D. Thompson and D.G. Higgins and T.J. Gibson},
title = {{CLUSTAL W}: improving the sensitivity of progressive multiple
sequence alignment through sequence weighting, position-specific
gap penalties and weight matrix choice},
journal = {Nucl. Acids Res.},
volume = 22,
pages = {4673-4680},
year = 1994
}

@article{PhyML,
author = {S. Guindon and O. Gascuel},
title = {A simple, fast, and accurate algorithm to estimate large phylogenies
by maximum likelihood},
journal = {Syst Biol.},
volume = 52,
number = 5,
pages = {696-704},
year = 2003
}

@unpublished{MosselSteel2003,
author = {E. Mossel and M. Steel},
title = { A phase transition for a random cluster model on 
phylogenetic trees},
note = {Submitted},
journal = { Mathematical Biosciences},
year = 2003
}

@article{Steel94,
author = {M.A. Steel},
title = {Recovering a tree from the leaf colorations it
generates under a Markov model},
journal = { Appl. Math. Lett.},
volume = {7},
number = 2,
pages = {19--24},
year = 1994
}

@unpublished{HusonKloepper2005,
author = {D.H. Huson and T.H. Kloepper},
title = {Computing Recombination Networks from Binary Sequences},
note = {To appear in: ECCB},
year = 2005
}


@article{RefinedBuneman2003,
author = {G.S. Brodal and R. Fagerberg and A. {\"O}stlin and C.N.S.Pedersen
and S.S. Rao},
title = {Computing Refined Buneman Trees in Cubic Time},
journal = {Lecture Notes in Computer Science},
note = {Springer Verlag},
volume = 2812,
pages = {259-270},
year = 2003
}

@unpublished{GambetteHuson2005,
author = {P. Gambette and D.H. Huson},
title = {Improved Layout of Phylogenetic Networks},
note = {Manuscript},
year = 2005
}

@article{FruchtermanReingold91,
author = {T. Fruchterman and E. Reingold},
title = {Graph drawing by force-directed placement},
journal = {Softw. - Pract. Exp.},
volume = 21,
number = 11,
pages = {1129-1164},
year = 1991
}

@article{Fitch1977,
author = {Walter M. Fitch},
title = {Phylogenies constrained by the crossover process as illustrated by human hemoglobins and a thirteen-cycle, eleven-amino-acid repeat in human apolipoprotein A-I},
journal = {Genetics},
volume = 86,
number = 3,
pages = {623-644},
year = 1977,
note = {\url{http://www.genetics.org/cgi/content/abstract/86/3/623}, lien v\'erifi\'e le 23/06/2006}
}

@article{Smith1976,
author = {George P. Smith},
title = {Evolution of repeated DNA sequences by unequal crossover},
journal = {Science},
volume = 191,
number = 4277,
pages = {528-535},
year = 1976,
note = {\url{http://www.sciencemag.org/cgi/content/abstract/191/4227/528}, lien v\'erifi\'e le 23/06/2006}
}

























































@unpublished{attiya1994,
author = {Hagit Attiya},
title = {Distributed Algorithms},
publisher = UM,
year = 1994,
note = {\url{http://people.ksp.sk/~misof/skola/Uvod\%20do\%20distribuovanych\%20algoritmov\%20(3ita\%204ita)/Attiya\%20-\%20Distributed\%20Algorithms.ps.gz}, lien v\'erifi\'e le 21/04/2006}
}


@article{burnspachl1989,
author = {James E. Burns and Jan K. Pachl},
title = {Uniform self-stabilizing rings},
journal = {ACM Transactions on Programming Languages and Systems},
pages = {330-344},
volume = 11,
year = 1989
}


@article{changroberts1979,
author = {Ernest Chang and Rosemary Roberts},
title = {An improved algorithm for decentralized extrema-finding in circular configurations of processes},
journal = {Communications of the ACM},
pages = {281-283},
volume = 22,
number = 5,
year = 1979
}


@book{diestel2005,
author = {Reinhard Diestel},
title = {Graph Theory, third (electronic) edition},
publisher = {Springer},
series = {New York Graduate Texts in Mathematics},
volume = 173,
year = 2005,
note = {\url{http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/GraphTheoryIII.pdf}, lien v\'erifi\'e le 21/04/2006}
}


@article{dijkstra1965,
author = {Edsger Wybe Dijkstra},
title = {Solution of a Problem in Concurrent Programming Control},
journal = {Communications of the ACM},
pages = {569},
volume = 8,
number = 9,
year = 1965
}


@article{huangbound,
author = {Stephen T. Hedetniemi and David P. Jacobs and Pradip K. Srimani},
title = {Maximal matching stabilizes in time $O(m)$},
journal = IPL,
pages = {221-223},
volume = 80,
number = 5,
year = 2001,
note = {\url{http://www.cs.clemson.edu/~stabiliz/Papers/matching-ipl-2001.pdf}, lien v\'erifi\'e le 21/04/2006}
}


@article{hsuhuang1992,
author = {Su-Chu Hsu and Shing-Tsaan Huang},
title = {A self-stabilizing algorithm for maximal matching},
journal = IPL,
pages = {77-81},
volume = 43,
number = 2,
year = 1992
}


@article{israelijalfon1993,
author = {Amos Israeli and Marc Jalfon},
title = {Uniform self-stabilizing ring orientation},
journal = {Information and Computation},
pages = {175-196},
volume = 104,
number = 2,
year = 1993
}


@inproceedings{lelann1977,
author = {G\'erard Le Lann},
title = {Distributed systems - Towards a formal approach},
booktitle = {1977 IFIP Congress Proceedings, Information Processing},
editor = {B. Gilchrist},
publisher = {North-Holland, Amsterdam},
pages = {155-160},
volume = 77,
year = 1977
}


@unpublished{lynchpattshamir1993,
author = {Nancy A. Lynch and Boaz Patt-Shamir},
title = {Distributed algorithms, lecture notes for 6.852},
publisher = UM,
year = 1992,
note = {\url{http://people.ksp.sk/~misof/skola/Uvod\%20do\%20distribuovanych\%20algoritmov\%20(3ita\%204ita)/Lynch\%20-\%20Distributed\%20Algorithms.ps.gz}, lien v\'erifi\'e le 21/04/2006}
}


@book{lynch1996,
author = {Nancy A. Lynch},
title = {Distributed algorithms},
publisher = {Morgan Kaufmann Publishers},
serie = {Morgan Kaufmann Series in Data Management Systems},
year = 1995,
}


@article{schneider1993,
author = {Marco Schneider},
title = {Self-stabilization},
journal = {ACM Computing Surveys},
pages = {45-67},
volume = 25,
number = 1,
year = 1993
}


@article{telmatching,
author = {Gerard Tell},
title = {Maximal Matching Stabilizes in Quadratic Time},
journal = IPL,
pages = {271-272},
volume = 49,
number = 6,
year = 1994
}


@book{tell1994,
author = {Gerard Tell},
title = {Introduction to Distributed Algorithms},
publisher = {Cambridge university Press},
year = 1994
}
\bibitem{telmatching} G. Tell : \emph{}, , 49, p. 271-272, 1994.


@article{bnr1996,
author = {Vineet Bafna and Babu O. Narayanan and R. Ravi},
title = {Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)},
journal = DAM,
pages = {41-54},
volume = 71,
number = 1,
year = 1996,
note = {\url{http://www.gsia.cmu.edu/afs/andrew/gsia/ravi/WWW/public/rectangle.ps}}
}
, lien v\'erifi\'e le 20/03/2006
%+ section 1 : introduction
%+ section 2 : motivation : alignement ADN
%+ section 3 : NP complétude de independent set de rectangles par réduction de 3 sat
%+ section 4 : MIS & ((d+1)-claw)-free graphs : algo t-opt heuristique d'amélioration gloutonne,
%+ ratio d'approximation < d/2+epsilon, pas mieux que d/2
%+ MWIS : ratio de t-opt < d-1+1/d, pas mieux que d-1-epsilon


@article{BOP2003,
author  = {J{\'o}zsef Balogh and Pascal Ochem and Andr{\'a}s Pluh{\'a}r},
title   = {On the Interval Number of Special Graphs},
journal = JGT,
pages   = {241-253},
volume  = 46,
year    = 2004,
note    = {\url{http://www.inf.u-szeged.hu/~pluhar/ieven.ps}}
}
, lien v\'erifi\'e le 19/04/2006

@inproceedings{bhnss2002,
author    = {Reuven Bar-Yehuda and Magn{\'u}s M. Halld{\'o}rson and Joseph Naor and Hadas Shachnai and Irina Shapira},
title     = {Scheduling Split Intervals},
booktitle = {13th Annual ACM-SIAM Symposium on Discrete Algorithms},
pages     = {732-741},
year      = 2002,
note      = {\url{http://www.cs.technion.ac.il/~reuven/PS/BarHal04.ps}}
}
, lien v\'erifi\'e le 13/03/2006
%+ section 1 : Exemples d'applis des t-int graphs : transmission media data, linear ressource alloc
%+ des t-uni graphs : multiseq similarity
%+ 
%+ MWIS APX-hard sur les (2,2) union graphs


@article{bekt2001,
author = {Jacek Blazewicz and Klaus H. Ecker and Tam{\'a}s Kis and Michal Tanas},
title = {A note on the complexity of scheduling coupled tasks on a single processor},
journal = {Journal of the Brazilian Computer Society},
year = 2001,
note = {\url{http://www.scielo.br/pdf/jbcos/v7n3/a04v7n3.pdf}}
}
, lien v\'erifi\'e le 13/03/2006
%+ 1|(1,h,1), \textrm{coupled, strict, prec, exact gap}|C_{\max}
%+ NP complet par réduction de coloration équilibrée
%+ Coloration équilibrée NP-complet par réduction de 3-PARTITION
%+ Rapport avec les graphes 2-intervallaires ??


@phdthesis{blin2005,
author = {Guillaume Blin},
title  = {Combinatoire et Bio-informatique : Comparaison de structures d'ARN et calcul de distances interg\'enomiques},
pages  = {77-99},
year = 2005,
school = {Universit{\'e} de Nantes},
note   = {\url{http://igm.univ-mlv.fr/~gblin/recherches/Publis/Phd_Guillaume_Blin.pdf}}
}
, lien v\'erifi\'e le 15/03/2006
% chapitre 3.2 : Approximabilité de 2IP (pp44-49)
% chapitre 6, idem que bfv2004


@inproceedings{bfv2004,
author    = {Guillaume Blin and Guillaume Fertin and St\'ephane Vialette},
title     = {New results for the 2-interval pattern problem},
booktitle = {Proceedings of the $15^{th}$ Symposium on Combinatorial Pattern Matching (CPM04)},
year      = 2004,
note      = {\url{http://www.sciences.univ-nantes.fr/info/perso/permanents/fertin/PAPERS/Blin_Fertin_Vialette_CPM04.pdf}}
}
, lien v\'erifi\'e le 13/03/2006

@conference{cw1996,
author = {Yi-Wu Chang and Douglas B. West},
title = {Interval Number and Boxicity of Directed Graphs},
journal = {Proceedings of 8th International Conference on Graph Theory},
year = 1996,
note = {\url{http://citeseer.ifi.unizh.ch/chang96interval.html}}
}
, lien v\'erifi\'e le 16/03/2006

@article{gw1979,
author = {Jerrold R. Griggs and Douglas B. West},
title = {Extremal values of the interval number of a graph},
journal = JADM,
pages = {1-7},
volume = 1,
year = 1979,
}


@unpublished{gyarfas2003,
author = {Andr\'as Gy{\'a}rf{\'a}s},
title = {Combinatorics of intervals, preliminary version},
journal = {IMA Summer Workshop on Combinatorics and Its Applications},
pages = {3,30-41},
note = {\url{http://www.math.gatech.edu/news/events/ima/newag.pdf}}
}
, lien v\'erifi\'e le 21/03/2006
% Exo 5 : faire le graphe d'intervalles en réunissant dans le mm coin
% les sommets avec le même chiffre, et tenter de trouver une
% k-coloration sur le graphe formé en recollant les sommets
% de même chiffre par paires
% Exo 6 : considérer chaque 2 intervalle comme deux sommets, il y a un
% seul graphe de degré 2 exactement (il n'y avait pas 3 gens en
% mm temps à la bibli) or ce n'est pas un graphe d'intervalles,
% c'est un vieux cycle.
% 


@article{gl1980,
author = {Andr\'as Gy{\'a}rf{\'a}s and Jen\"o Lehel},
title = {Covering and coloring problems for relatives of intervals},
journal = DM,
pages = {167-180},
volume = 55,
year = 1985,
}


@inbook{gl1970,
editor = {P. Erd\"os and A. Rényi and V.T. S\'os},
author = {Andr\'as Gy{\'a}rf{\'a}s and Jen\"o Lehel},
title = {A Helly-type problem in trees},
booktitle = {Combinatorial Theory and its Application},
pages = {571-584},
publisher = {North-Holland, Amsterdam},
year = 1970,
}
% relations between matching number \nu and transversal number \tau


@article{gw1995,
author = {Andr\'as Gy{\'a}rf{\'a}s and Douglas B. West},
title = {Multitrack Interval Graphs},
journal = CG,
year = 1995,
volume = 109,
pages = {109-116},
note = {\url{http://www.math.uiuc.edu/~west/pubs/tracks.ps}}
}
, lien v\'erifi\'e le 21/03/2006

@inproceedings{jmt1992,
author = {Deborah Joseph and Joao Meidanis and Prasoon Tiwari},
title = {Determining DNA Sequence Similarity Using Maximum Independent Set Algorithms for Interval Graphs},
journal = {3rd Scandinavian Workshop on Algorithm Theory},
pages = {326-337},
booktitle = {Lecture Notes in Computer Science},
volume = 621,
year = 1992,
}

@article{kaiser1997,
author = {Tom{\'a}s Kaiser},
title = {Transversals of d-Intervals},
journal = {Discrete and Computational Geometry},
volume = 18,
number = 2,
year = 1997,
note = {\url{http://www.springerlink.com/link.asp?id = gn67lv27h5jacx4q}}
}
, lien v\'erifi\'e le 16/03/2006

@unpublished{karlsson2005,
author = {Ragnar Karlsson},
title = {A Survey of Split Intervals and Related Graphs},
journal = UM,
year = 2005,
note = {\url{http://www.hi.is/~rkk1/SplitSurvey.pdf}}
}
, lien v\'erifi\'e le 16/03/2006

@article{kw1997,
author = {Alexandr V. Kostochka and Douglas B. West},
title = {Total Interval Number for Graphs with Bounded Degree},
journal = JGT,
pages = {79-84},
volume = 25,
year = 1997,
note = {\url{http://citeseer.ifi.unizh.ch/kostochka95total.html}}
}
, lien v\'erifi\'e le 16/03/2006
% décomposition du graphe outerplanar par parcours en largeur
% en ensembles de sommets à distance paire ou non d'une
% racine. Les deux ensembles, unions de chemins disjoints,
% sont placés sur des lignes différentes,
% puis les arêtes entre les 2 ensembles sont traduites
% en utilisant l'intervalle restant des 2-intervalles.


@article{kw1999,
author = {Alexandr V. Kostochka and Douglas B. West},
title = {Every Outerplanar Graph is the Union of Two Interval Graphs},
journal = CN,
volume = 139,
pages = {5-8},
year = 1999,
note = {\url{http://citeseer.ifi.unizh.ch/297772.html}}
}
, lien v\'erifi\'e le 16/03/2006

@article{kw1993,
author = {Thomas M. Kratzke and Douglas B. West},
title = {The total interval number of a graph I: Fundamental Classes},
journal = DM,
volume = 118,
pages = {145-156},
year = 1993,
}

@article{kw1996,
author = {T.M. Kratzke and Douglas B. West},
title = {The total interval number of a graph II: Trees and complexity},
journal = JDM,
volume = 9,
year = 1996,
pages = {339-348},
note = {\url{www.math.uiuc.edu/~west/pubs/titrees.pdf}}
}
, lien v\'erifi\'e le 16/03/2006

@article{op1997,
author = {A.J. Orman and C.N. Potts},
title = {On the Complexity of Coupled-Task Scheduling},
journal = DAM,
volume = 72,
year = 1997,
pages = {141-154}
}


@article{osm1998,
author = {A.J. Orman and A.K. Shahani and A.R. Moore},
title = {Modelling for the control of a complex radar system},
journal = {Computers and operations research},
year = 1998,
note = {\url{http://dx.doi.org/10.1016/S0305-0548(97)00047-6}}
}
, lien v\'erifi\'e le 15/03/2006

@article{shapiro1980,
author = {R.D. Shapiro},
title = {Scheduling Coupled Tasks},
journal = {Naval Research Logistics Quarterly},
volume = 27,
year = 1980,
pages = {489-498},
}


@article{tardos1995,
author = {G. Tardos},
title = {Transversals of 2-intervals, a topological approach},
journal = C,
volume = 15,
number = 1,
year = 1995,
pages = {123-134}
}


@article{Vialette2004,
author = {St{\'e}phane Vialette},
title = {On the computational complexity of 2-interval pattern matching problems},
journal = TCS,
volume = 312,
number = {2-3},
year = 2004,
note = {\url{http://dx.doi.org/10.1016/j.tcs.2003.08.010}}
}
, lien v\'erifi\'e le 15/03/2006

@article{ws1984,
author = {Douglas B. West and David B. Shmoys},
title = {Recognizing graphs with fixed interval number is {NP}-complete},
journal = DAM,
volume = 8,
year = 1984,
pages = {295-305}
}


@book{Fishburn1985,
author = {Peter C. Fishburn},
title = {Interval Orders and Interval Graphs},
publisher = {John Wiley \& Sons},
serie = {Wiley-Interscience Series in Discrete Mathematics},
year = {1985}
}
1 Introduction defines partial orders, weak orders, posets, considers graph as posets
 irreflexive binary relation : not xRx
 negatively transitive : xRy = > for all z, xRz or zRy
 partial order : R irreflexive transitive
 weak order : R asymmetric negatively transitive
 linear order : R weak complete
2 Interval orders :
 < such that (a<x && b<y) = > (a<y || b<x) (matrix such that at least one 1 in each row & column)
 partial semiorder : ( a<b && b<c) = > (a<x || x<c) (matrix such that no 1 above/right of another 1)
 x <^- y : left end of x precedes left end of y
 x <^+ y : right end of x precedes right end of y
 = > define an order <_0 on the endpoints (X,-) = x^- and (X,+) = x^+
 <_0 is a weak order if < is an interval order

@TECHREPORT{Gardi2003,
 AUTHOR = {Fr\'ed\'eric Gardi},
 TITLE = {{A note on the Roberts characterization of proper and unit interval graphs}},
 INSTITUTION = {{LIF}},
 ADDRESS = {Marseille, France},
 TYPE = {Research report},
 NUMBER = {11-2003},
 MONTH = {January},
 YEAR = {2003},
 NOTE = {\url{http://www.lif-sud.univ-mrs.fr/Rapports/11-2003.html}},
}
, lien v\'erifi\'e le 10/05/2006
% quite short proof that (proper = unit) interval graphs.


@manuscript{wood2006,
author = {David R. Wood},
title = {Characterisations of Intersection Graphs by Vertex Orderings},
journal = UM,
year = 2006,
note = {\url{http://arxiv.org/PS_cache/cs/pdf/0404/0404031.pdf}}
}
, lien v\'erifi\'e le 11/05/2006
% bandwidth of a graph: order its vertices, maximum distance between two vertices joined by an edge
% lower bound : degree/2
% upper bounds for interval, proper interval, cocomparability, AT-free, split graphs.
% analysis of the bandwidth of chordal and comparability graphs


@manuscript{dsw2005,
author = {Vida Dujmovi\'c and Matthew Suderman and David R. Wood},
title = {Really Straight Drawings II: Non-Planar Graphs},
journal = UM,
year = 2005,
note = {\url{http://cgm.cs.mcgill.ca/~vida/pubs/papers/ReallyStraight-Nonplanar.pdf}}
}
, lien v\'erifi\'e le 11/05/2006
% slope number : minimum number of different slopes while drawing a graph : upper and lower bounds
% or approximations, for some graph classes.


@article{chorsudan1998,
author = {Benny Chor and Madhu Sudan},
title = {A geometric approach to betweenness},
journal = JDM,
volume = 11,
number = 4,
year = 1998,
note = {\url{http://epubs.siam.org/SIDMA/volume-11/art_29622.html}}
}
lien v\'erifi\'e le 12/05/2006
% reduction of MaxCut to Betweenness


@inproceedings{micalivazirani1980,
author = {Silvio Micali and Vijay V. Vazirani},
title = {An ${O}(\sqrt{|v|} |E|)$ Algorithm for Finding Maximum Matching in General Graphs},
booktitle = {Proceedings of the 21th Annual IEEE Symposium on Foundation of Computer Science},
year = 1980,
pages = {17-27}
}
% difficult algorithm, according to Michel Habib
% implementation here: http://archi.snu.ac.kr/bwkim/free-OR-codes.html#cardmatch


@phdthesis{Evans1999,
author = {Patricia A. Evans},
title  = {Algorithms and Complexity for Annotated Sequence Analysis},
year   = 1999,
school = {University of Victoria},
note   = {\url{http://www.cs.unb.ca/profs/pevans/research/pae-thesis.ps}}
}
lien v\'erifi\'e le 18/05/2006
% Chapter 1 definitions : subsequence, substrings, DNA...
% Chapter 2 "Background" : state of the art on sequence comparison & aligning, protein 3D structure,
 parametrized complexity.
% Chapter 3 "Types of annotation" : colouring, arcs and eventual restrictions, edit distances between annotated
 sequences.
% Chapter 4 Annotation verification, automatas and coloured regular languages
% Chapter 5 Annotation Creation : format conversions (colourings, arc formats)
% Chapter 6 Comparing coloured sequences : cartesian product of the alphabets or more subtile.
% Chapter 7 Comparing Arc-annotated Sequences, problem \Pi of finding longest common subsequence
 between two arc-annotated sequences which respects order and presence of arcs
 and various restrictions, NP completeness from IndependentSet for pi(unlim,plain)
 from clique for pi(cross,cross), fixed-parameter (cutwidth = max number of arcs
 that cross or end at some point in the sequence) algorithm.
% Chapter 8 Variations of the algorithm by weighting the arcs, and/or extending them to cover many
 nucleotides.
 
@article{bkkm1999,
author = {Hajo Broersma and Ton Kloks and Dieter Kratsch and Haiko M\"uller},
title = {Independent sets in asteroidal triple-free graphs},
journal = JDM,
volume = 12,
number = 2,
year = 1999,
pages = {276-287},
note = {\url{http://epubs.siam.org/fulltext/SIDMA/volume-12/32634.pdf}}
}
, lien v\'erifi\'e le 18/05/2006
% O(n^4) algorithm solving IndependentSet on AT-free graphs.


@article{dushnikmiller1941,
author = {Ben Dushnik and Edwin W. Miller},
title = {Partially ordered sets},
journal = {American Journal of Mathematics},
volume = 63,
year = 1941,
pages = {600-610}
}
% Some mathematical stuff supposed to prove that a permutation graph = a comparability + cocompar. graph


@manuscript{BiedlLectureNotes,
author = {Therese Biedl},
title = {Graph-theoretic Algorithms},
journal = UM,
year = 2005,
note = {\url{http://www.student.cs.uwaterloo.ca/~cs762/Notes/book.pdf}}
}
lien v\'erifi\'e le 23/05/2006
% course about graphs, lot of stuff on interval graphs in the beginning, planar graphs after that


@phdthesis{Vialette2001,
author = {St\'ephane Vialette},
title  = {Aspects algorithmiques de la pr\'ediction des structures secondaires d'ARN},
year   = 2001,
school = {Universit{\'e} Paris 7},
note   = {\url{http://philippe.gambette.free.fr/LIAFA/Vialette2001.htm}}
}
% Chapter 6 : 2-intervals


@article{trotterharary1979,
author = {William T. Trotter and Frank Harary},
title = {On double and multiple interval graphs},
journal = JGT,
volume = 3,
pages = {205-211},
year = 1979
}


@article{hararykabell1980,
author = {Frank Harary and Jerald Allan Kabell},
title = {An Intuitive Approach to Interval Numbers of Graphs},
journal = {Mathematics Magazine},
volume = 53,
number = 1,
pages = {39-44},
year = 1980
}

@Book{ BLS1999,
 author = {Andreas Brandst{\"a}dt and Van Bang Le and Jeremy P. Spinrad},
 title = {Graph Classes: a Survey},
 publisher = {SIAM Monographs on Discrete Mathematics and Applications},
 year = 1999,
}


@misc{isgci,
author = {Andreas Brandst{\"a}dt and Van Bang Le and Thomas Szymczak and Frank Siegemund and H.N. de Ridder and Stefan Knorr and Mirko Rzehak and M. Mowitz and Natalia Ryabova},
title = {{ISGCI}: {Information System on Graph Class Inclusions}},
note = {\url{http://wwwteo.informatik.uni-rostock.de/isgci/classes.cgi}}
}
, lien v\'erifi\'e le 29/05/2006

@article{gll1982,
author   = {Udaiprakash I. Gupta and D. T. Lee and Joseph Y.-T Leung},
title    = {Efficient Algorithms for Interval Graphs and Circular-Arc Graphs},
journal  = {Networks},
volume   = 12,
pages    = {459-467},
year     = 1982
}

@article{fmw1997,
author = {Stefan Felsner and Rudolf M\"uller and Lorenz Wernisch},
title = {Trapezoid Graphs and Generalizations, Geometry and Algorithms},
journal = DAM,
volume = 74,
number = 1,
year = {1997},
pages = {13-32},
note = {\url{ftp://ftp.inf.fu-berlin.de/pub/reports/tr-b-94-02.ps.gz}},
}
, lien v\'erifi\'e le 30/05/2006

@book{CLR1990,
 author = {Thomas Cormen and Charles Leiserson and Ronald Rivest},
 title = {Introduction to Algorithms},
 year = 1990,
 publisher = {MIT Press}
 }

@article{Edmonds1965,
 author = {Jack Edmonds},
 title = {Paths, trees and flowers},
 journal = {Canadian Journal of Mathematics},
 volume = 17,
 year = 1965,
 pages = {449-467}
 }

@article{Galil1986,
 author = {Zviv Galil},
 title = {Efficient algorithms for finding maximum matching in graphs},
 journal = {ACM Computing Surveys},
 volume = 18,
 number = 1,
 year = 1986,
 pages = {23-38},
 note = {\url{http://doi.acm.org/10.1145/6462.6502}}
}
, lien v\'erifi\'e le 01/06/2006
% weighted or not, edmonds algorithm, idea of Micali & Vazirani

@book{FordFulkerson1962,
author = {Lester R. Ford and Delbert R. Fulkerson},
title = {Flows In Networks},
publisher = {Princeton University Press},
year = {1962}
}

@article{COS1997AT,
author = {Derek G. Corneil and Stephan Olariu and Lorna Stewart},
title = {Asteroidal Triple-Free Graphs},
journal = JDM,
year = {1997},
note = {\url{http://epubs.siam.org/fulltext/SIDMA/volume-10/25012.pdf}}
}
, lien v\'erifi\'e le 01/06/2006

@article{GLS1981,
 author = {Martin Gr{\"o}tschel and L{\'a}szlo Lov{\'a}sz and Alexander Schrijver},
 title = {The ellipsoid method and its consequences in combinatorial optimization},
 journal = C,
 volume = 1,
 number = 2,
 pages = {169-197},
 year = 1981,
 note = {\url{http://www.zib.de/groetschel/pubnew/paper/groetschellovaszschrijver1981a.djvu}}
}
 lien v\'erifi\'e le 01/06/2006
%To find the independent set on i don't remember which kind of graphs (perfect?)


@article{COS1995,
author = {Derek G. Corneil and Stephan Olariu and Lorna Stewart},
title = {Simple Linear Time Recognition of Unit Interval Graphs},
journal = {IPL},
volume = 55,
year = 1995,
pages = {99-104},
note = {\url{http://www.cs.odu.edu/~olariu/uig.ps}}
}
lien v\'erifi\'e le 07/06/2006
Algorithm avoiding to check first that the graph is an interval graph.
It realizes a BFS to check that a characteristic condition for
uig defined by Roberts is verified: there exists an ordering of the vertices such that the
neighbourhood of each vertex is an interval in this ordering (if you have a realization of
the graph, the ordering is for example the ordering on the left endpoints)


@inproceedings{EKSX1996,
author = {Martin Ester and Hans-Peter Kriegel and J\"org Sander and Xiaowei Xu},
title = {A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise},
booktitle = {Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining (KDD96)},
year = 1996,
pages = {226-231},
note = {\url{http://ifsc.ualr.edu/xwxu/publications/kdd-96.pdf}}
}
lien v\'erifi\'e le 08/06/2006
606 Google Scholar Citations in 2006...
criterion to put a point p in a cluster C :
- there are enough points of C in the neighborhood of p
FAILS ! (because of the density of points lower on the frontier
of the cluster).
Instead :
- there is a point q in the neighborhood of p that has enough
points of C in its neighborhood.
 = > Efficient implementation (O(n log n)) thanks to efficient
region queries with R* trees.


@inproceedings{BKSS1990,
author = {Norbert Beckmann and Hans-Peter Kriegel and Ralf Schneider and Bernhard Seeger},
title = {The $R^*$-tree: an efficient and robust access method for points and rectangles},
booktitle = {Proceedings of the 1990 ACM SIGMOD international conference on Management of data},
year = 1990,
pages = {322-331},
note = {\url{http://www.sai.msu.su/~megera/postgres/gist/papers/Rstar3.pdf}}
}
lien v\'erifi\'e le 08/06/2006
structure for efficient region queries.

@article{CrickWatson1953,
author = {James D. Watson and Francis H. Crick},
title = {Molecular Structure of nucleic acides, a structure for deoxyribose nucleic acid},
journal = {Nature},
year = 1953,
note = {\url{http://www.annals.org/cgi/reprint/138/7/581.pdf}}
}
lien v\'erifi\'e le 09/06/2006
They explain that they doubt that DNA is a 3-chain molecule and propose their helix structure
with the pairing nucleotides.


@article{Holyer1981,
author = {Ian Holyer},
title = {The {NP}-completeness of Edge-Colouring},
journal = JOC,
volume = 10,
number = 4,
year = 1981,
pages= {718-720},
note = {\url{http://www.cs.bris.ac.uk/~ian/graphs/edge.pdf}}
}
lien v\'erifi\'e le 15/06/2006

@manuscript{Sloane,
  author =       {Neil J. A. Sloane},
  title =        {The on-line encyclopedia of integer sequences},
  note =         {\url{http://www.research.att.com/~njas/sequences/}}
}

@inproceedings{CHLV2005,
  author    = {Maxime Crochemore and Danny Hermelin and Gad M. Landau and St{\'e}phane Vialette},
  title     = {Approximating the 2-Interval Pattern Problem},
  booktitle = {Algorithms - ESA 2005, 13th Annual European Symposium},
  series    = {Lecture Notes in Computer Science},
  volume    = {3669},
  year      = {2005},
  pages     = {426-437},
  note      = {\url{http://dx.doi.org/10.1007/11561071_39}},
}
, lien v\'erifi\'e le 28/06/2006

@article{Polya1937,
  author    = {George P{\'o}lya},
  title     = {Kombinatorische Anzahlbestimmungen f{\"u}r Gruppen, Graphen, und chemische Verbindungen},
  journal   = {Acta Mathematica},
  volume    = 68,
  pages     = {145-254},
  year      = 1937
  }
  
@book{Harary1969,
  author    = {Frank Harary},
  title     = {Graph Theory},
  publisher = {Addison-Wesley},
  year      = 1969
  }

@phdthesis{Montgolfier2003,
  author    = {Fabien de Montgolfier},
  title     = {D{\'e}composition modulaire des graphes, th{\'e}orie, extensions et algorithmes},
  school    = {Universit{\'e} Montpellier II},  
  year      = 2003,
  note      = {\url{http://www.liafa.jussieu.fr/~fm/publications/memoire.pdf}}
}
lien v\'erifi\'e le 03/07/2006

@book{GareyJohnson1979,
  author    = {Michael~R. Garey and David.~S. Johnson},
  title     = {Computers and Intractability, a guide to the theory of {NP}-completeness},
  publisher = {Bell Telephone Laboratories, Inc.},
  year      = 1979
}

@article{Lehot1974,
  author    = {Philippe G. H. Lehot},
  title     = {An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph},
  journal   = JACM,
  volume    = 21,
  number    = 4,
  pages     = {569-575},
  year      = 1974,
  note      = {\url{http://doi.acm.org/10.1145/321850.321853}}
}
 lien v\'erifi\'e le 06/07/2006
 
@article{Berge1994,
  author    = {Claude Berge},
  title     = {Qui a tu{\'e} le duc de {Densmore} ?},
  journal   = {Biblioth{\`e}que {Oulipienne}},
  volume    = 67,
  year      = 1994,
  note      = {r{\'e}{\'e}dition Castor Astral, 2000}
}

@article{BoothLueker1976,
  author    = {Kellogg S. Booth and George S. Lueker},
  title     = {Testing for the consecutive ones property, interval graphs, and graph planarity using {PQ}-tree algorithms},
  journal   = {J. Comp. Sys. Sci.},
  volume    = 13,
  year      = 1976,
  pages     = {335-379}
}

@article{Kendall1969,
  author    = {David G. Kendall},
  title     = {Incidence matrices, interval graphs, and seriation in archaeology},
  journal   = {Pacific Journal of Mathematics},
  volume    = 28,
  year      = 1969,
  pages     = {565-570},
  note      = {\url{http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1102983306}}
}
lien v\'erifi\'e le 24/07/2006
Tries to solve the "approximate" consecutive ones problems.
Consecutive 1 property = Petrie matrix | Robinson matrix = going left or down from the diagonal, never increase.
sigma0 row permutation applied on M gives a Petrie => sigma0 applied to row and columns of M tM fives a Robinson.
+ proof
Idea of using MultiDimensional Scaling to solve approximate consecutive ones problem.

@article{FG1965,
  author    = {D. R. Fulkerson and O. A. Gross},
  title     = {Incidence matrices, interval graphs, and seriation in archaeology},
  journal   = {Pacific Journal of Mathematics},
  volume    = 28,
  year      = 1969,
  pages     = {565-570},
  note      = {\url{http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1102995572}}
}
lien v\'erifi\'e le 24/07/2006
Tries to solve the "approximate" consecutive ones problems.
Consecutive 1 property = Petrie matrix | Robinson matrix = going left or down from the diagonal, never increase.
sigma0 row permutation applied on M gives a Petrie => sigma0 applied to row and columns of M tM fives a Robinson.
+ proof
Idea of using MultiDimensional Scaling to solve approximate consecutive ones problem.

@inproceedings{KMMS2003,
  author    = {Dieter Kratsch and Ross M. McConnell and Kurt Mehlhorn and Jeremy P. Spinrad},
  title     = {Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs},
  booktitle = {Proceedings of the fourteenth annual ACM-SIAM Symposium on Discrete algorithms (SODA'03)},
  year      = 2003,
  pages     = {158-167},
  note      = {\url{http://www.cs.colostate.edu/~rmm/certificates.pdf}}
}
algorithm+certificate for permutation and interval graphs in linear time.
lien v\'erifi\'e le 24/07/2006

@article{Spinrad1994,
  author    = {Jeremy P. Spinrad},
  title     = {Recognition of circle graphs},
  journal   = {Journal of Algorithms},
  volume    = 16,
  number    = 2,
  year      = 1994,
  pages     = {264-282},
}

@phdthesis{Gardi2005,
  author    = {Fr{\'e}d{\'e}ric Gardi},
  title     = {Ordonnancement avec exclusion mutuelle par un graphe d'intervalles ou d'une classe apprent{\'e}e :
               complexit{\'e} et algorithmes},
  school    = {Universit{\'e} de la M{\'e}diterran{\'e}e - Aix-Marseille II},
  year      = 2005,
  note      = {\url{http://www.lif-sud.univ-mrs.fr/~gardi/downloads/These_Gardi.pdf}}
}
26/07/2006

@article{MS1994,
  author    = {Tze-Heng Ma and Jeremy P. Spinrad},
  title     = {On the 2-chain subgraph cover and related problems},
  journal   = {Journal of Algorithms},
  volume    = 17,
  number    = 2,
  year      = 1994,
  pages     = {251-268},
}
D'après Corneil, algo un peu compliqué (variation de celui de Cogis qui reconnaît les graphes
de dimension intervallaire 2)

@inproceedings{MS1991,
  author    = {Tze-Heng Ma and Jeremy P. Spinrad},
  title     = {An ${O}(n^2)$ time algorithm for the 2-chain cover problem and related problems},
  booktitle = {Proceedings of the second annual ACM-SIAM Symposium on Discrete algorithms (SODA'91)},  
  year      = 1991,
  pages     = {363-372},
  note      = {\url{http://portal.acm.org/citation.cfm?id=127852}}
}
02/08/2006

@phdthesis{Cogis1980,
  author    = {Olivier Cogis},
  title     = {La dimension Ferrers des graphes orient{\'e}s},
  school    = {Universit{\'e} Pierre et Marie Curie},
  year      = 1980,
}

@article{Cogis1982,
  author    = {Olivier Cogis},
  title     = {Ferrers Dimension of a Digraph},
  journal   = DM,
  volume    = 38,
  number    = 1,
  year      = 1982,
  pages     = {47-52},
}

@article{CC1996,
  author    = {Faithful Hoe Kooi Cheah and Derek Corneil},
  title     = {On the structure of trapezoid graphs},
  journal   = DAM,
  volume    = 66,
  number    = 2,
  year      = 1996,
  pages     = {109-133},
}

@book{Forte1973,
  author    = {Allen Forte},
  title     = {The structure of atonal music},
  publisher = {Yale University Press},
  year      = 1973
}

@article{StapleButcher2005,
  author    = {David W. Staple and Samuel E. Butcher},
  title     = {Pseudoknots: {RNA} Structures with Diverse Functions},
  journal   = {{PLoS Biology}},
  volume    = 3,
  number    = 6,
  year      = 2005,
  pages     = {109-133},
  note      = {\url{http://biology.plosjournals.org/perlserv/?request=get-document&doi=10.1371/journal.pbio.0030213}}  
}
  , lien v\'erifi\'e le 07/08/2006

@article{RPPBB1982,
  author    = {Krijn Rietveld and R. Van Poelgeest and Cornelis W.A. Pleij and J.H. Van Boom and Leendert Bosch},
  title     = {The {tRNA}-like structure at the 3' terminus of turnip yellow mosaic virus {RNA}, differences and similarities with canonical {tRNA}},
  journal   = NAR,
  volume    = 10,
  year      = 1982,
  pages     = {1929-1946}
}

++ Dans ~stewart/GRAPH/circle/circle.bib
Independent set in circle graph : 
Gavril 73 O(n^3)
Hsu 85 O(n^2+m log log n)
Apostolico, Atallah, Hambrusch O(n^2) clique 1992

Recognition

@article{AAH1992,
  author    = {Alberto Apostolico and Mikhail J. Atallah and Susanne E. Hambrusch},
  title     = {New clique and independent set algorithms for circle graphs},
  journal   = DAM,
  volume    = 36,
  number    = 2,
  year      = 1992,
  pages     = {1-24}
}
O(n^2)


@inproceedings{Tiskin2006,
  author    = {Alexander Tiskin},
  title     = {Semi-local longest common subsequences and maximum cliques in circle graphs},
  booktitle = {Proceedings of CPM2006, Lecture Notes in Computer Science},
  volume    = 4009,
  year      = 2006,
  pages     = {271-282},
  note      = {\url{http://www.dcs.warwick.ac.uk/~tiskin/pub/2006/circle.pdf}}
}
lien v\'erifi\'e le 24/08/2006
O(n^2)

@inproceedings{LiLi2006,
  author    = {Shuai-Cheng Li and Ming Li},
  title     = {On the Complexity of the Crossing Contact Map Pattern Matching Problem},
  booktitle = {Proceedings of 6th Workshop on Algorithms in Bioinformatics (WABI 2006)},
  year      = 2006
}
This problem is in fact NP-complete, bugged alggorithm in Gramm2002

@inproceedings{Gramm2004,
  author    = {Jens Gramm},
  title     = {A polynomial-time algorithm for the matching of crossing contact-map patterns},
  booktitle = {Proceedings of the 4th International Workshop on Algorithms in Bioinformatics (WABI 2004), Lecture Notes in Bioinformatics},
  volume    = 3240,
  year      = 2004,
  pages     = {38-49},
  note      = {\url{http://portal.acm.org/citation.cfm?id=1042198.1042361}}
}
lien v\'erifi\'e le 25/08/2006

@mastersthesis{Bouvel2006,
  author    = {Mathilde Bouvel},
  title     = {Autour des permutations s{\'e}parables},
  year      = 2006,
  school    = {ENS Cachan, MPRI},
  note      = {\url{http://philippe.gambette.free.fr/LIAFA/Bouvel2006.htm}},
}

@article{YannakakisGavril1980,
  author    = {Mihalis Yannakakis and Fanica Gavril},
  title     = {Edge dominating sets in graphs},  
  journal   = JAM,
  volume    = 38,
  number    = 3,
  pages     = {364-372},
  year      = 1980,
  note      = {\url{http://www.jstor.org/view/00361399/di974726/97p0339h/}}
}
26/08/2006

@article{HTC1992,
  author    = {Ju Yuan Hsiao and Chuan Yi Tang and Ruay Shiung Chang},
  title     = {An Efficient Algorithm for Finding a Maximum Weight 2-Independent
               Set on Interval Graphs},
  journal   = IPL,
  volume    = {43},
  number    = {5},
  year      = {1992},
  pages     = {229-235},
}

@article{Lin2006,
  author    = {Yaw-Ling Lin},
  title     = {Circular and Circle Trapezoid Graphs},
  journal   = {Journal of Science and Engineering Technology},
  volume    = 2,
  number    = 2,
  year      = 2006,
  pages     = {11-17},
  note      = {\url{http://journal.dyu.edu.tw/dyujo/document/s2-2-11-17.pdf}}
}
26/08/2006


@article{APT1979,
  author    = {Bengt Aspvall and Michael F. Plass and Robert E. Tarjan},
  title     = {A linear-time algorithm for testing the truth of certain quantified boolean formulas},
  journal   = IPL,
  year      = 1979,
}
Nice algorithm to solve 2-SAT using an digraph.


@article{CPS2006,
  author    = {Peter Cameron and Thomas Prellberg and Dudley Stark},
  title     = {Asymptotic enumeration of incidence matrices},
  journal   = {Journal of Physics: Conference Series},
  volume    = {42},
  pages     = {59-70},
  year      = 2006,
  note      = {\url{http://ej.iop.org/links/r8JtBU4n_/st_AleI52xG2ZV7Sav5vpA/jpconf6_42_007.pdf}}
}
01/09/2006
nice maths (Möbius inversion, sum re-indicing) to enumerate certain adjacency matrices

@article{BenderGoldman1975,
  author    = {Edward A. Bender and Jay R. Goldman},
  title     = {On the Applications of Moebius Inversion in Combinatorial Analysis},
  journal   = {American Mathematical Monthly},
  volume    = {82},
  number    = {8},
  pages     = {789-803},
  year      = 1975,
  note      = {\url{http://www.citeulike.org/user/euclid/article/775065}}
}
01/09/2006


@inproceedings{KMR1972,
  author    = {Richard M. Karp and Raymond E. Miller and Arnold L. Rosenberg},
  title     = {Rapid identification of repeated patterns in strings, trees and arrays},
  booktitle   = {Proceedings of the 4th Annual ACM Symposium},
  pages     = {125-136},
  year      = 1972,
  note      = {\url{http://doi.acm.org/10.1145/800152.804905}}
}

@manuscript{Makinen1999,
  author    = {Erkki M{\"a}kinen},
  title     = {On The Longest Upsequence Problem For Permutations},
  year      = 1999,
  note      = {\url{http://citeseer.ist.psu.edu/225912.html}}
}
03/09/2006