{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T09:45:25Z","timestamp":1777455925643,"version":"3.51.4"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2014,6,25]],"date-time":"2014-06-25T00:00:00Z","timestamp":1403654400000},"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":["Acta Informatica"],"published-print":{"date-parts":[[2014,10]]},"DOI":"10.1007\/s00236-014-0202-1","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T07:35:01Z","timestamp":1403595301000},"page":"449-471","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Exploiting a hypergraph model for finding Golomb rulers"],"prefix":"10.1007","volume":"51","author":[{"given":"Manuel","family":"Sorge","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hannes","family":"Moser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathias","family":"Weller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,6,25]]},"reference":[{"issue":"7","key":"202_CR1","doi-asserted-by":"crossref","first-page":"524","DOI":"10.1016\/j.jcss.2009.09.002","volume":"76","author":"FN Abu-Khzam","year":"2010","unstructured":"Abu-Khzam, F.N.: A kernelization algorithm for $$d$$ d -hitting set. J. Comput. Syst. Sci. 76(7), 524\u2013531 (2010)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"202_CR2","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7(4), 567\u2013583 (1986)","journal-title":"J. Algorithms"},{"key":"202_CR3","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1002\/j.1538-7305.1953.tb01422.x","volume":"32","author":"W Babcock","year":"1953","unstructured":"Babcock, W.: Intermodulation interference in radio systems. Bell Syst. Tech. J. 32, 63\u201373 (1953)","journal-title":"Bell Syst. Tech. J."},{"issue":"1","key":"202_CR4","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1137\/S0097539797323716","volume":"29","author":"C Bertram-Kretzberg","year":"1999","unstructured":"Bertram-Kretzberg, C., Lefmann, H.: The algorithmic aspects of uncrowded hypergraphs. SIAM J. Comput. 29(1), 201\u2013230 (1999)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"202_CR5","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1109\/PROC.1977.10517","volume":"65","author":"G Bloom","year":"1977","unstructured":"Bloom, G., Golomb, S.: Applications of numbered undirected graphs. Proc. IEEE 65(4), 562\u2013570 (1977)","journal-title":"Proc. IEEE"},{"key":"202_CR6","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1109\/TAP.1974.1140732","volume":"22","author":"E Blum","year":"1974","unstructured":"Blum, E., Biraud, F., Ribes, J.: On optimal synthetic linear arrays with applications to radioastronomy. IEEE Trans. Antennas Propag. 22, 108\u2013109 (1974)","journal-title":"IEEE Trans. Antennas Propag."},{"key":"202_CR7","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: Kernelization: new upper and lower bound techniques. In: Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC \u201909). Lecture Notes in Computer Science, vol. 5917, pp. 17\u201337. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-11269-0_2"},{"key":"202_CR8","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/s10601-007-9020-1","volume":"12","author":"C Cotta","year":"2007","unstructured":"Cotta, C., Dot\u00fa, I., Fern\u00e1ndez, A.J., Hentenryck, P.V.: Local search-based hybrid algorithms for finding Golomb rulers. Constraints 12, 263\u2013291 (2007)","journal-title":"Constraints"},{"key":"202_CR9","doi-asserted-by":"crossref","unstructured":"Dell, H., van Melkebeek, D.: Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. In: Proceedings of the 42th Annual ACM Symposium on Theory of Computing (STOC \u201910), pp. 251\u2013260. ACM. Journal version to appear in Journal of the ACM (2010)","DOI":"10.1145\/1806689.1806725"},{"key":"202_CR10","unstructured":"Dimitromanolakis, A.: Analysis of the Golomb Ruler and the Sidon Set Problems, and Determination of Large, Near-Optimal Golomb Rulers. Master\u2019s thesis, Department of Electronic and Computer Engineering, Technical University of Crete (2002)"},{"key":"202_CR11","unstructured":"Distributed.net. Home page. http:\/\/www.distributed.net\/ . Accessed May 2014"},{"issue":"1","key":"202_CR12","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1109\/18.651068","volume":"44","author":"A Dollas","year":"1998","unstructured":"Dollas, A., Rankin, W.T., McCracken, D.: A new algorithm for Golomb ruler derivation and proof of the 19 mark ruler. IEEE Trans. Inf. Theory 44(1), 379\u2013382 (1998)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"202_CR13","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/j.jda.2009.08.001","volume":"8","author":"M Dom","year":"2010","unstructured":"Dom, M., Guo, J., H\u00fcffner, F., Niedermeier, R., Truss, A.: Fixed-parameter tractability results for feedback set problems in tournaments. J. Discrete Algorithms 8(1), 76\u201386 (2010)","journal-title":"J. Discrete Algorithms"},{"key":"202_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Berlin (2013)"},{"issue":"3","key":"202_CR15","doi-asserted-by":"crossref","first-page":"235","DOI":"10.3934\/amc.2009.3.235","volume":"3","author":"K Drakakis","year":"2009","unstructured":"Drakakis, K.: A review of the available construction methods for Golomb rulers. Adv. Math. Commun. 3(3), 235\u2013250 (2009)","journal-title":"Adv. Math. Commun."},{"issue":"3","key":"202_CR16","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1016\/j.ejc.2012.04.008","volume":"34","author":"MR Fellows","year":"2013","unstructured":"Fellows, M.R., Jansen, B.M.P., Rosamond, F.A.: Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. Eur. J. Comb. 34(3), 541\u2013566 (2013)","journal-title":"Eur. J. Comb."},{"key":"202_CR17","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"issue":"1","key":"202_CR18","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. ACM SIGACT News 38(1), 31\u201345 (2007)","journal-title":"ACM SIGACT News"},{"issue":"1","key":"202_CR19","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/j.jda.2010.07.003","volume":"9","author":"C Komusiewicz","year":"2011","unstructured":"Komusiewicz, C., Niedermeier, R., Uhlmann, J.: Deconstructing intractability\u2014a multivariate complexity analysis of interval constrained coloring. J. Discrete Algorithms 9(1), 137\u2013151 (2011)","journal-title":"J. Discrete Algorithms"},{"key":"202_CR20","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Misra, N., Saurabh, S.: Kernelization\u2014preprocessing with a guarantee. In: The Multivariate Algorithmic Revolution and Beyond\u2014Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday. Lecture Notes in Computer Science, vol. 7370, pp. 129\u2013161. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-30891-8_10"},{"key":"202_CR21","doi-asserted-by":"crossref","unstructured":"Malakonakis, P., Sotiriades, E., Dollas, A.: GE3: a single FPGA client-server architecture for Golomb ruler derivation. In: Proceedings of the International Conference on Field-Programmable Technology (FPT \u201910), pp. 470\u2013473. IEEE (2010)","DOI":"10.1109\/FPT.2010.5681461"},{"key":"202_CR22","doi-asserted-by":"crossref","first-page":"738","DOI":"10.1016\/j.dam.2008.07.006","volume":"157","author":"C Meyer","year":"2008","unstructured":"Meyer, C., Papakonstantinou, P.A.: On the complexity of constructing Golomb rulers. Discrete Appl. Math. 157, 738\u2013748 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"202_CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2006.10.002","volume":"370","author":"F Nicolas","year":"2007","unstructured":"Nicolas, F., Rivals, E.: Longest common subsequence problem for unoriented and cyclic strings. Theor. Comput. Sci. 370(1\u20133), 1\u201318 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"202_CR24","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"202_CR25","unstructured":"Niedermeier, R.: Reflections on multivariate algorithmics and problem parameterization. In: Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS \u201910), volume 5 of Dagstuhl Seminar Proceedings, pp. 17\u201332. IBFI Dagstuhl, Germany (2010)"},{"key":"202_CR26","doi-asserted-by":"crossref","unstructured":"Pereira, F., Tavares, J., Costa, E.: Golomb rulers: the advantage of evolution. In: Proceedings of the 11th Portuguese Conference on Artificial Intelligence (EPIA \u201903). Lecture Notes in Computer Science, vol. 2902, pp. 29\u201342. Springer, Berlin (2003)","DOI":"10.1007\/978-3-540-24580-3_11"},{"key":"202_CR27","unstructured":"Rankin, W.T.: Optimal Golomb rulers: An Exhaustive Parallel Search Implementation. Master\u2019s thesis, Department of Electrical Engineering, Duke University, Durham. Addendum by Aviral Singh (1993)"},{"key":"202_CR28","unstructured":"Soliday, S.W., Homaifar, A., Lebby, G.L.: Genetic algorithm approach to the search for Golomb rulers. In: Proceedings of the 6th International Conference on Genetic Algorithms (ICGA \u201995), pp. 528\u2013535. Morgan Kaufmann, Burlington (1995)"},{"key":"202_CR29","unstructured":"Sorge, M.: Algorithmic Aspects of Golomb Ruler Construction. Studienarbeit, Institut f\u00fcr Informatik, Friedrich-Schiller-Universit\u00e4t Jena, Germany, 2010. Available electronically. arXiv:1005.5395v2"},{"key":"202_CR30","doi-asserted-by":"crossref","unstructured":"Sorge, M., Moser, H., Niedermeier, R., Weller, M.: Exploiting a hypergraph model for finding Golomb rulers. In: Proceedings of the 2nd International Symposium on Combinatorial Optimization (ISCO \u201912). Lecture Notes in Computer Science, vol. 7422, pp. 368\u2013379. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-32147-4_33"},{"key":"202_CR31","doi-asserted-by":"crossref","unstructured":"Tavares, J., Pereira, F., Costa, E.: Golomb rulers: a fitness landscape analysis. In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC \u201908), pp. 3695\u20133701. IEEE (2008)","DOI":"10.1109\/CEC.2008.4631298"},{"key":"202_CR32","doi-asserted-by":"crossref","unstructured":"van Bevern, R.: Towards optimal and expressive kernelization for $$d$$ d -hitting set. Algorithmica (2013)","DOI":"10.1007\/s00453-013-9774-3"},{"key":"202_CR33","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1090\/S0002-9939-1978-0500555-0","volume":"72","author":"J Gathen von zur","year":"1978","unstructured":"von zur Gathen, J., Sieveking, M.: A bound on solutions of linear integer equations and inequalities. Proc. Am. Math. Soc. 72, 155\u2013158 (1978)","journal-title":"Proc. Am. Math. Soc."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-014-0202-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-014-0202-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-014-0202-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,11]],"date-time":"2019-08-11T21:19:37Z","timestamp":1565558377000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-014-0202-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,25]]},"references-count":33,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2014,10]]}},"alternative-id":["202"],"URL":"https:\/\/doi.org\/10.1007\/s00236-014-0202-1","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,6,25]]}}}