{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T01:17:31Z","timestamp":1725585451408},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642215803"},{"type":"electronic","value":"9783642215810"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-21581-0_12","type":"book-chapter","created":{"date-parts":[[2011,6,10]],"date-time":"2011-06-10T09:30:19Z","timestamp":1307698219000},"page":"134-144","source":"Crossref","is-referenced-by-count":1,"title":["A Satisfiability-Based Approach for Embedding Generalized Tanglegrams on Level Graphs"],"prefix":"10.1007","author":[{"given":"Ewald","family":"Speckenmeyer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Wotzlaw","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Porschen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"12_CR1","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B. Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.E.: A linear-time algorithm for testing the truth of certain quantified Boolean formulas. Information Processing Letters\u00a08(3), 121\u2013123 (1979)","journal-title":"Information Processing Letters"},{"key":"12_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/978-3-642-00727-9_13","volume-title":"Bioinformatics and Computational Biology","author":"M.S. Bansal","year":"2009","unstructured":"Bansal, M.S., Chang, W., Eulenstein, O., Fern\u00e1ndez-Baca, D.: Generalized binary tanglegrams: Algorithms and applications. In: Rajasekaran, S. (ed.) BICoB 2009. LNCS, vol.\u00a05462, pp. 114\u2013125. Springer, Heidelberg (2009)"},{"key":"12_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/978-3-642-00219-9_32","volume-title":"Graph Drawing","author":"K. Buchin","year":"2009","unstructured":"Buchin, K., Buchin, M., Byrka, J., N\u00f6llenburg, M., Okamoto, Y., Silveira, R.I., Wolff, A.: Drawing (complete) binary tanglegrams: Hardness, approximation, fixed-parameter tractability. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol.\u00a05417, pp. 324\u2013335. Springer, Heidelberg (2009)"},{"key":"12_CR4","unstructured":"Cha, B., Iwama, K., Kambayashi, Y., Miyazaki, S.: Local search algorithms for partial MAXSAT. In: Proceedings of the 14th National Conference on Artificial Intelligence (AAAI\/IAAI), pp. 263\u2013268 (1997)"},{"key":"12_CR5","first-page":"65","volume-title":"Tangled Trees: Phylogeny, Cospeciation and Coevolution","author":"M.A. Charleston","year":"2003","unstructured":"Charleston, M.A., Parkins, S.L.: Lizards, malaria, and jungles in the Caribbean. In: Tangled Trees: Phylogeny, Cospeciation and Coevolution, pp. 65\u201392. University of Chicago Press, Chicago (2003)"},{"issue":"2-3","key":"12_CR6","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/PL00008273","volume":"25","author":"B. DasGupta","year":"1999","unstructured":"DasGupta, B., He, X., Jiang, T., Li, M., Tromp, J.: On the linear-cost subtree-transfer distance between phylogenetic trees. Algorithmica\u00a025(2-3), 176\u2013195 (1999)","journal-title":"Algorithmica"},{"key":"12_CR7","volume-title":"Graph Drawing: Algorithms for Geometric Representations of Graphs","author":"G. Battista Di","year":"1998","unstructured":"Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for Geometric Representations of Graphs. Prentice-Hall, Englewood Cliffs (1998)"},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"2596","DOI":"10.1093\/bioinformatics\/bti325","volume":"21","author":"J. Dufayard","year":"2005","unstructured":"Dufayard, J., Duret, L., Penel, S., Gouy, M., Rechenmann, F., Perriere, G.: Tree pattern matching in phylogenetic trees: automatic search for orthologs or paralogs in homologous gene sequence databases. Bioinformatics\u00a021, 2596\u20132603 (2005)","journal-title":"Bioinformatics"},{"issue":"4","key":"12_CR9","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BF01187020","volume":"11","author":"P. Eades","year":"1994","unstructured":"Eades, P., Wormald, N.C.: Edge crossings in drawings of bipartite graphs. Algorithmica\u00a011(4), 379\u2013403 (1994)","journal-title":"Algorithmica"},{"issue":"7","key":"12_CR10","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1016\/j.jcss.2009.10.014","volume":"76","author":"H. Fernau","year":"2010","unstructured":"Fernau, H., Kaufmann, M., Poths, M.: Comparing trees via crossing minimization. Journal of Computer and System Sciences\u00a076(7), 593\u2013608 (2010)","journal-title":"Journal of Computer and System Sciences"},{"key":"12_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"issue":"3","key":"12_CR12","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1137\/0604033","volume":"4","author":"M.R. Garey","year":"1983","unstructured":"Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods\u00a04(3), 312\u2013316 (1983)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"issue":"4","key":"12_CR13","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"Hopcroft, J., Tarjan, R.E.: Efficient planarity testing. J. ACM\u00a021(4), 549\u2013568 (1974)","journal-title":"J. ACM"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Reed, B.A.: Computing crossing number in linear time. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pp. 382\u2013390 (2007)","DOI":"10.1145\/1250790.1250848"},{"key":"12_CR15","unstructured":"Leipert, S.: Level planarity testing and embedding in linear time. Ph.D. thesis, Institut f\u00fcr Informatik, Universit\u00e4t zu K\u00f6ln (1998)"},{"key":"12_CR16","volume-title":"Tangled Trees: Phylogeny, Cospeciation, and Coevolution","author":"R.D.M. Page","year":"2002","unstructured":"Page, R.D.M.: Tangled Trees: Phylogeny, Cospeciation, and Coevolution. University of Chicago Press, Chicago (2002)"},{"issue":"11","key":"12_CR17","doi-asserted-by":"publisher","first-page":"1408","DOI":"10.1016\/j.dam.2007.02.010","volume":"155","author":"S. Porschen","year":"2007","unstructured":"Porschen, S., Speckenmeyer, E.: Satisfiability of mixed Horn formulas. Discrete Applied Mathematics\u00a0155(11), 1408\u20131419 (2007)","journal-title":"Discrete Applied Mathematics"},{"key":"12_CR18","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/S1571-0653(04)00327-0","volume":"9","author":"B. Randerath","year":"2001","unstructured":"Randerath, B., Speckenmeyer, E., Boros, E., Hammer, P.L., Kogan, A., Makino, K., Simeone, B., Cepek, O.: A satisfiability formulation of problems on level graphs. Electronic Notes in Discrete Mathematics\u00a09, 269\u2013277 (2001)","journal-title":"Electronic Notes in Discrete Mathematics"},{"issue":"3","key":"12_CR19","first-page":"24","volume":"3","author":"E. Speckenmeyer","year":"2010","unstructured":"Speckenmeyer, E., Porschen, S.: PARTIAL MAX-SAT of level graph (mixed-Horn)formulas. Studies in Logic\u00a03(3), 24\u201343 (2010)","journal-title":"Studies in Logic"},{"issue":"4","key":"12_CR20","doi-asserted-by":"publisher","first-page":"588","DOI":"10.1109\/TCBB.2010.57","volume":"7","author":"B. Venkatachalam","year":"2010","unstructured":"Venkatachalam, B., Apple, J., St. John, K., Gusfield, D.: Untangling tanglegrams: Comparing trees by their drawings. IEEE\/ACM Transactions on Computational Biology and Bioinformatics\u00a07(4), 588\u2013597 (2010)","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing - SAT 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21581-0_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,1,19]],"date-time":"2019-01-19T11:35:59Z","timestamp":1547897759000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21581-0_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642215803","9783642215810"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21581-0_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}