{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T19:30:00Z","timestamp":1779305400283,"version":"3.51.4"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,11,21]],"date-time":"2016-11-21T00:00:00Z","timestamp":1479686400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Agence Nationale de la Recherche (FR)","award":["ANR-11-LABX-0031-01"],"award-info":[{"award-number":["ANR-11-LABX-0031-01"]}]},{"name":"Agence Nationale de la Recherche (FR)","award":["ANR-13-BS02-0007"],"award-info":[{"award-number":["ANR-13-BS02-0007"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,1]]},"DOI":"10.1007\/s00453-016-0243-7","type":"journal-article","created":{"date-parts":[[2016,11,21]],"date-time":"2016-11-21T14:01:32Z","timestamp":1479736892000},"page":"209-233","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On the Complexity of Compressing Two Dimensional Routing Tables with Order"],"prefix":"10.1007","volume":"80","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3727-051X","authenticated-orcid":false,"given":"Fr\u00e9d\u00e9ric","family":"Giroire","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fr\u00e9d\u00e9ric","family":"Havet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joanna","family":"Moulierac","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,11,21]]},"reference":[{"issue":"1","key":"243_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s101070100271","volume":"92","author":"S Arora","year":"2002","unstructured":"Arora, S., Frieze, A., Kaplan, H.: A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. Math. Program. 92(1), 1\u201336 (2002)","journal-title":"Math. Program."},{"key":"243_CR2","volume-title":"Space Decomposition Techniques for Fast Layer-4 Switching","author":"MM Buddhikot","year":"2000","unstructured":"Buddhikot, M.M., Suri, S., Waldvogel, M.: Space Decomposition Techniques for Fast Layer-4 Switching. Springer, Boston (2000)"},{"key":"243_CR3","doi-asserted-by":"crossref","unstructured":"Cohen, R., Lewin-Eytan, L., Naor, J., Raz, D.: On the effect of forwarding table size on SDN network utilization. In: IEEE INFOCOM, pp. 1734\u20131742 (2014)","DOI":"10.1109\/INFOCOM.2014.6848111"},{"key":"243_CR4","unstructured":"Eppstein, D., Muthukrishnan, S.: Internet packet filter management and rectangle geometry. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 827\u2013835 (2001)"},{"issue":"3","key":"243_CR5","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/BF02020271","volume":"9","author":"T Gallai","year":"1958","unstructured":"Gallai, T.: Maximum-minimum s\u00e4tze \u00fcber graphen. Acta Math. Hung. 9(3), 395\u2013434 (1958)","journal-title":"Acta Math. Hung."},{"key":"243_CR6","unstructured":"Giroire, F., Havet, F., Moulierac, J.: Compressing Two-dimensional Routing Tables with Order. Research Report RR-8658, INRIA Sophia Antipolis (2014)"},{"key":"243_CR7","unstructured":"Giroire, F., Havet, F., Moulierac, J.: Compressing two-dimensional routing tables with order. In: INOC (International Network Optimization Conference). Varsovie (2015). https:\/\/hal.inria.fr\/hal-01162724"},{"key":"243_CR8","doi-asserted-by":"crossref","unstructured":"Giroire, F., Moulierac, J., Khoa\u00a0Phan, T.: Optimizing Rule Placement in Software-Defined Networks for Energy-aware Routing. In: IEEE GLOBECOM. IEEE, Austin (2014)","DOI":"10.1109\/GLOCOM.2014.7037187"},{"issue":"2","key":"243_CR9","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.ipl.2006.11.016","volume":"102","author":"J Guo","year":"2007","unstructured":"Guo, J., H\u00fcffner, F., Moser, H.: Feedback arc set in bipartite tournaments is np-complete. Inf. Process. Lett. 102(2), 62\u201365 (2007)","journal-title":"Inf. Process. Lett."},{"key":"243_CR10","doi-asserted-by":"crossref","unstructured":"Hari, A., Suri, S., Parulkar, G.: Detecting and resolving packet filter conflicts. In: INFOCOM 2000, pp. 1203\u20131212. IEEE (2000)","DOI":"10.1109\/INFCOM.2000.832496"},{"key":"243_CR11","doi-asserted-by":"crossref","unstructured":"Hoffman, A.J., Kruskal, J.B.: Integral boundary points of convex polyhedra. In: 50 Years of Integer Programming 1958\u20132008, pp. 49\u201376. Springer (2010)","DOI":"10.1007\/978-3-540-68279-0_3"},{"key":"243_CR12","doi-asserted-by":"crossref","unstructured":"Kang, N., Liu, Z., Rexford, J., Walker, D.: Optimizing the \u201cone big switch abstraction\u201d in software-defined networks. In: Proceedings of CoNEXT, pp. 13\u201324. ACM, New York (2013)","DOI":"10.1145\/2535372.2535373"},{"key":"243_CR13","unstructured":"Kanizo, Y., Hay, D., Keslassy, I.: Palette: Distributing tables in software-defined networks. In: Proceedings of IEEE INFOCOM, 2013, pp. 545\u2013549 (2013)"},{"key":"243_CR14","unstructured":"Kann, V.: On the approximability of np-complete optimization problems. Ph.D. thesis, Royal Institute of Technology Stockholm (1992)"},{"key":"243_CR15","volume-title":"Reducibility Among Combinatorial Problems","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility Among Combinatorial Problems. Springer, New York (1972)"},{"issue":"2","key":"243_CR16","doi-asserted-by":"crossref","first-page":"1251","DOI":"10.1109\/TNET.2015.2407831","volume":"24","author":"K Kogan","year":"2016","unstructured":"Kogan, K., Nikolenko, S.I., Rottenstreich, O., Culhane, W., Eugster, P.: Exploiting order independence for scalable and expressive packet classification. IEEE\/ACM Trans. Netw. 24(2), 1251\u20131264 (2016)","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"4","key":"243_CR17","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1145\/285243.285283","volume":"28","author":"T Lakshman","year":"1998","unstructured":"Lakshman, T., Stiliadis, D.: High-speed policy-based packet forwarding using efficient multi-dimensional range matching. ACM SIGCOMM Compu. Commun. Rev. 28(4), 203\u2013214 (1998)","journal-title":"ACM SIGCOMM Compu. Commun. Rev."},{"issue":"2","key":"243_CR18","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1145\/1355734.1355746","volume":"38","author":"N McKeown","year":"2008","unstructured":"McKeown, N., Anderson, T., Balakrishnan, H., Parulkar, G., Peterson, L., Rexford, J., Shenker, S., Turner, J.: Openflow: Enabling innovation in campus networks. SIGCOMM Comput. Commun. Rev. 38(2), 69\u201374 (2008)","journal-title":"SIGCOMM Comput. Commun. Rev."},{"key":"243_CR19","doi-asserted-by":"crossref","unstructured":"Narayanan, R., Kotha, S., Lin, G., Khan, A., Rizvi, S., Javed, W., Khan, H., Khayam, S.: Macroflows and microflows: Enabling rapid network innovation through a split sdn data plane. In: 2012 European Workshop on Software Defined Networking (EWSDN), pp. 79\u201384 (2012)","DOI":"10.1109\/EWSDN.2012.16"},{"key":"243_CR20","doi-asserted-by":"crossref","unstructured":"Rifai, M., Huin, N., Caillouet, C., Giroire, F., Lopez-Pacheco, D., Moulierac, J., Urvoy-Keller, G.: Too many sdn rules? Compress them with minnie. In: 2015 IEEE Global Communications Conference (GLOBECOM), pp. 1\u20137. IEEE (2015)","DOI":"10.1109\/GLOCOM.2015.7417661"},{"issue":"1","key":"243_CR21","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1109\/TNET.2014.2382031","volume":"24","author":"O Rottenstreich","year":"2016","unstructured":"Rottenstreich, O., Keslassy, I., Hassidim, A., Kaplan, H., Porat, E.: Optimal in\/out tcam encodings of ranges. IEEE\/ACM Trans. Netw. 24(1), 555\u2013568 (2016)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"243_CR22","doi-asserted-by":"crossref","unstructured":"Rottenstreich, O., et al.: Lossy compression of packet classifiers. In: Proceedings of the Eleventh ACM\/IEEE Symposium on Architectures for networking and communications systems, pp. 39\u201350. IEEE Computer Society (2015)","DOI":"10.1109\/ANCS.2015.7110119"},{"key":"243_CR23","doi-asserted-by":"crossref","unstructured":"Stephens, B., Cox, A., Felter, W., Dixon, C., Carter, J.: Past: Scalable ethernet for data centers. In: Proceedings of CoNEXT, pp. 49\u201360. ACM, New York (2012)","DOI":"10.1145\/2413176.2413183"},{"issue":"4","key":"243_CR24","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/s00453-002-1000-7","volume":"35","author":"S Suri","year":"2003","unstructured":"Suri, S., Sandholm, T., Warkhede, P.: Compressing two-dimensional routing tables. Algorithmica 35(4), 287\u2013300 (2003)","journal-title":"Algorithmica"},{"issue":"3","key":"243_CR25","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1145\/1108956.1108958","volume":"37","author":"DE Taylor","year":"2005","unstructured":"Taylor, D.E.: Survey and taxonomy of packet classification techniques. ACM Comput. Surv. (CSUR) 37(3), 238\u2013275 (2005)","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"243_CR26","doi-asserted-by":"crossref","unstructured":"Van Zuylen, A.: Linear programming based approximation algorithms for feedback set problems in bipartite tournaments. In: Chen, J., Cooper, S.B. (eds.) Theory and Applications of Models of Computation: 6th Annual Conference, TAMC 2009, Changsha, China, May 18-22, 2009. Proceedings, vol 5532, pp 370\u2013379. Springer Berlin Heidelberg (2009)","DOI":"10.1007\/978-3-642-02017-9_39"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0243-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0243-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0243-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,15]],"date-time":"2019-09-15T16:37:31Z","timestamp":1568565451000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0243-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,21]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["243"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0243-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,21]]}}}