{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:43:09Z","timestamp":1742913789880,"version":"3.40.3"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030046507"},{"type":"electronic","value":"9783030046514"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-04651-4_10","type":"book-chapter","created":{"date-parts":[[2018,11,15]],"date-time":"2018-11-15T19:56:50Z","timestamp":1542311810000},"page":"138-153","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Generating Algebraic Expressions for Labeled Grid Graphs"],"prefix":"10.1007","author":[{"given":"Mark","family":"Korenblit","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,11,16]]},"reference":[{"key":"10_CR1","volume-title":"Mathematical Recreations and Essays","author":"WWR Ball","year":"1987","unstructured":"Ball, W.W.R., Coxeter, H.S.M.: Mathematical Recreations and Essays, 13th edn. The Macmillan Company, Dover, New York (1987)","edition":"13"},{"key":"10_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/978-3-642-11476-2_4","volume-title":"Structural Information and Communication Complexity","author":"A Bar-Noy","year":"2010","unstructured":"Bar-Noy, A., Cheilaris, P., Lampis, M., Mitsou, V., Zachos, S.: Ordered coloring grids and related graphs. In: Kutten, S., \u017derovnik, J. (eds.) SIROCCO 2009. LNCS, vol. 5869, pp. 30\u201343. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-11476-2_4"},{"issue":"2\u20133","key":"10_CR3","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0166-218X(86)90037-5","volume":"15","author":"WW Bein","year":"1986","unstructured":"Bein, W.W., Brucker, P.: Greedy concepts for network flow problems. Discret. Appl. Math. 15(2\u20133), 135\u2013144 (1986)","journal-title":"Discret. Appl. Math."},{"issue":"6","key":"10_CR4","doi-asserted-by":"publisher","first-page":"1112","DOI":"10.1137\/0221065","volume":"21","author":"WW Bein","year":"1992","unstructured":"Bein, W.W., Kamburowski, J., Stallmann, M.F.M.: Optimal reduction of two-terminal directed acyclic graphs. SIAM J. Comput. 21(6), 1112\u20131129 (1992)","journal-title":"SIAM J. Comput."},{"key":"10_CR5","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0022-247X(65)90125-3","volume":"10","author":"RJ Duffin","year":"1965","unstructured":"Duffin, R.J.: Topology of series-parallel networks. J. Math. Anal. Appl. 10, 303\u2013318 (1965)","journal-title":"J. Math. Anal. Appl."},{"issue":"2","key":"10_CR6","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/0304-3975(96)00035-7","volume":"162","author":"L Finta","year":"1996","unstructured":"Finta, L., Liu, Z., Milis, I., Bampis, E.: Scheduling UET-UCT series-parallel graphs on two processors. Theor. Comput. Sci. 162(2), 323\u2013340 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"10_CR7","first-page":"519","volume-title":"Boolean Functions: Theory, Algorithms and Applications","author":"MC Golumbic","year":"2011","unstructured":"Golumbic, M.C., Gurvich, V.: Read-once functions. In: Crama, Y., Hammer, P.L. (eds.) Boolean Functions: Theory, Algorithms and Applications, pp. 519\u2013560. Cambridge University Press, New York (2011)"},{"issue":"10","key":"10_CR8","doi-asserted-by":"publisher","first-page":"1465","DOI":"10.1016\/j.dam.2005.09.016","volume":"154","author":"MC Golumbic","year":"2006","unstructured":"Golumbic, M.C., Mintz, A., Rotics, U.: Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial k-trees. Discret. Appl. Math. 154(10), 1465\u20131477 (2006)","journal-title":"Discret. Appl. Math."},{"key":"10_CR9","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0012-365X(79)90131-6","volume":"28","author":"MC Golumbic","year":"1979","unstructured":"Golumbic, M.C., Perl, Y.: Generalized Fibonacci maximum path graphs. Discret. Math. 28, 237\u2013245 (1979)","journal-title":"Discret. Math."},{"issue":"3","key":"10_CR10","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF01432359","volume":"41","author":"M Gr\u00f6tschel","year":"1995","unstructured":"Gr\u00f6tschel, M., Martin, A., Weismantel, R.: Routing in grid graphs by cutting planes. ZOR - Math. Methods Oper. Res. 41(3), 255\u2013275 (1995)","journal-title":"ZOR - Math. Methods Oper. Res."},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/BF01164636","volume":"12","author":"H Hosoya","year":"1993","unstructured":"Hosoya, H., Harary, F.: On the matching properties of three fence graphs. J. Math. Chem. 12, 211\u2013218 (1993)","journal-title":"J. Math. Chem."},{"issue":"1","key":"10_CR12","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BF01294263","volume":"11","author":"S Irani","year":"1994","unstructured":"Irani, S.: Coloring inductive graphs on-line. Algorithmica 11(1), 53\u201372 (1994)","journal-title":"Algorithmica"},{"key":"10_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/3-540-58325-4_199","volume-title":"Algorithms and Computation","author":"M Kaufmann","year":"1994","unstructured":"Kaufmann, M., Gao, S., Thulasiraman, K.: On Steiner minimal trees in grid graphs and its application to VLSI routing. In: Du, D.-Z., Zhang, X.-S. (eds.) ISAAC 1994. LNCS, vol. 834, pp. 351\u2013359. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/3-540-58325-4_199"},{"issue":"2","key":"10_CR14","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1137\/S0097539789162109","volume":"23","author":"M Kaufmann","year":"1998","unstructured":"Kaufmann, M., Mehlhorn, K.: A linear-time algorithm for the homotopic routing problem in grid graphs. SIAM J. Comput. 23(2), 227\u2013246 (1998)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10_CR15","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1137\/S0097539793255709","volume":"25","author":"LM Kirousis","year":"1996","unstructured":"Kirousis, L.M., Thilikos, D.M.: The linkage of a graph. SIAM J. Comput. 25(3), 626\u2013647 (1996)","journal-title":"SIAM J. Comput."},{"key":"10_CR16","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.dam.2016.01.011","volume":"228","author":"M Korenblit","year":"2017","unstructured":"Korenblit, M.: Decomposition methods for generating algebraic expressions of full square rhomboids and other graphs. Discret. Appl. Math. 228, 60\u201372 (2017)","journal-title":"Discret. Appl. Math."},{"key":"10_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/3-540-45066-1_17","volume-title":"Discrete Mathematics and Theoretical Computer Science","author":"M Korenblit","year":"2003","unstructured":"Korenblit, M., Levit, V.E.: On algebraic expressions of series-parallel and Fibonacci graphs. In: Calude, C.S., Dinneen, M.J., Vajnovszki, V. (eds.) DMTCS 2003. LNCS, vol. 2731, pp. 215\u2013224. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-45066-1_17"},{"key":"10_CR18","unstructured":"Krause, A.: Bounded Treewidth Graphs - A Survey German Russian Winter School, St. Petersburg, Russia (2003). http:\/\/wwwmayr.in.tum.de\/konferenzen\/Jass03\/presentations\/krause.pdf"},{"key":"10_CR19","unstructured":"Levit, V.E., Korenblit, M.: A symbolic approach to scheduling of robotic lines. In: Intelligent Scheduling of Robots and Flexible Manufacturing Systems. The Center for Technological Education Holon, Israel, pp. 113\u2013125 (1996)"},{"issue":"1\u20133","key":"10_CR20","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/j.dam.2005.02.007","volume":"149","author":"A Mintz","year":"2005","unstructured":"Mintz, A., Golumbic, M.C.: Factoring Boolean functions using graph partitioning. Discret. Appl. Math. 149(1\u20133), 131\u2013153 (2005)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"10_CR21","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1287\/moor.4.3.215","volume":"4","author":"CL Monma","year":"1979","unstructured":"Monma, C.L.: Sequencing with series-parallel precedence constraints. Math. Oper. Res. 4(3), 215\u2013224 (1979)","journal-title":"Math. Oper. Res."},{"key":"10_CR22","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/0196-8858(91)90030-M","volume":"12","author":"D Mundici","year":"1991","unstructured":"Mundici, D.: Solution of Rota\u2019s problem on the order of series-parallel networks. Adv. Appl. Math. 12, 455\u2013463 (1991)","journal-title":"Adv. Appl. Math."},{"key":"10_CR23","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1016\/S0196-8858(03)00088-5","volume":"32","author":"M Noy","year":"2004","unstructured":"Noy, M., Rib\u00f3, A.: Recursively constructible families of graphs. Adv. Appl. Math. 32, 350\u2013363 (2004)","journal-title":"Adv. Appl. Math."},{"key":"10_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/978-3-642-03848-8_7","volume-title":"Business Process Management","author":"MK Oikawa","year":"2009","unstructured":"Oikawa, M.K., Ferreira, J.E., Malkowski, S., Pu, C.: Towards algorithmic generation of business processes: from business step dependencies to process algebra expressions. In: Dayal, U., Eder, J., Koehler, J., Reijers, H.A. (eds.) BPM 2009. LNCS, vol. 5701, pp. 80\u201396. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03848-8_7"},{"issue":"4","key":"10_CR25","doi-asserted-by":"publisher","first-page":"818","DOI":"10.1137\/0214057","volume":"14","author":"A Satyanarayana","year":"1985","unstructured":"Satyanarayana, A., Wood, R.K.: A linear time algorithm for computing K-terminal reliability in series-parallel networks. SIAM J. Comput. 14(4), 818\u2013832 (1985)","journal-title":"SIAM J. Comput."},{"key":"10_CR26","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<349::AID-RSA9>3.0.CO;2-V","volume":"13","author":"P Savicky","year":"1998","unstructured":"Savicky, P., Woods, A.R.: The number of Boolean functions computed by formulas of a given size. Rand. Struct. Algorithms 13, 349\u2013382 (1998)","journal-title":"Rand. Struct. Algorithms"},{"issue":"4","key":"10_CR27","doi-asserted-by":"publisher","first-page":"972","DOI":"10.1137\/S0097539795288489","volume":"27","author":"JP Schmidt","year":"1998","unstructured":"Schmidt, J.P.: All highest scoring paths in weighted grid graphs and their application to finding all approximate repeats in strings. SIAM J. Comput. 27(4), 972\u2013992 (1998)","journal-title":"SIAM J. Comput."},{"key":"10_CR28","unstructured":"Sesh Kumar, K.S.: Convex relaxations for learning bounded-treewidth decomposable graphs. In: Proceedings of 30th International Conference on Machine Learning (ICML2013), JMLR: W&CP, vol. 28 (2013)"},{"key":"10_CR29","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/BF01581240","volume":"59","author":"A Tamir","year":"1993","unstructured":"Tamir, A.: A strongly polynomial algorithm for minimum convex separable quadratic cost flow problems on two-terminal series-parallel networks. Math. Program. 59, 117\u2013132 (1993)","journal-title":"Math. Program."},{"issue":"5","key":"10_CR30","doi-asserted-by":"publisher","first-page":"837","DOI":"10.1016\/0026-2714(83)91008-9","volume":"23","author":"JA Wald","year":"1983","unstructured":"Wald, J.A., Colbourn, C.J.: Steiner trees in probabilistic networks. Microelectron. Reliabil. 23(5), 837\u2013840 (1983)","journal-title":"Microelectron. Reliabil."},{"key":"10_CR31","unstructured":"Wang, A.R.R.: Algorithms for multilevel logic optimization. Ph.D. thesis, University of California, Berkeley (1989)"},{"key":"10_CR32","unstructured":"Weisstein, E.W.: Grid Graph From MathWorld - A Wolfram Web Resource. http:\/\/mathworld.wolfram.com\/GridGraph.html"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-04651-4_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T15:47:15Z","timestamp":1710344835000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-04651-4_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030046507","9783030046514"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-04651-4_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"16 November 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Atlanta, GA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 December 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/spacl.kennesaw.edu\/cocoa2018\/cfp.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}