{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:21Z","timestamp":1759637901797},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642169250"},{"type":"electronic","value":"9783642169267"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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":[[2010]]},"DOI":"10.1007\/978-3-642-16926-7_22","type":"book-chapter","created":{"date-parts":[[2010,11,10]],"date-time":"2010-11-10T02:48:26Z","timestamp":1289357306000},"page":"232-243","source":"Crossref","is-referenced-by-count":14,"title":["Measuring Indifference: Unit Interval Vertex Deletion"],"prefix":"10.1007","author":[{"given":"Ren\u00e9","family":"van Bevern","sequence":"first","affiliation":[]},{"given":"Christian","family":"Komusiewicz","sequence":"additional","affiliation":[]},{"given":"Hannes","family":"Moser","sequence":"additional","affiliation":[]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"22_CR1","doi-asserted-by":"publisher","first-page":"178","DOI":"10.2307\/1905751","volume":"24","author":"R.D. Luce","year":"1956","unstructured":"Luce, R.D.: Semiorders and a theory of utility discrimination. Econometrica\u00a024, 178\u2013191 (1956)","journal-title":"Econometrica"},{"key":"22_CR2","series-title":"Studies in Economic Theory","volume-title":"Utility Maximization, Choice and Preference","author":"F. Aleskerov","year":"2007","unstructured":"Aleskerov, F., Bouyssou, D., Monjardet, B.: Utility Maximization, Choice and Preference. Studies in Economic Theory, vol.\u00a016. Springer, Heidelberg (2007)"},{"key":"22_CR3","first-page":"139","volume-title":"Proof Techniques in Graph Theory","author":"F.S. Roberts","year":"1969","unstructured":"Roberts, F.S.: Indifference graphs. In: Proof Techniques in Graph Theory, pp. 139\u2013146. Academic Press, New York (1969)"},{"key":"22_CR4","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1111\/j.1749-6632.1979.tb17778.x","volume":"328","author":"F.S. Roberts","year":"1979","unstructured":"Roberts, F.S.: Indifference and seriation. Annals of the New York Academy of Sciences\u00a0328, 173\u2013182 (1979)","journal-title":"Annals of the New York Academy of Sciences"},{"key":"22_CR5","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph classes: a survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey. SIAM, Philadelphia (1999)"},{"key":"22_CR6","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"J.M. Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J.\u00a0Comput. System Sci.\u00a020, 219\u2013230 (1980)","journal-title":"J.\u00a0Comput. System Sci."},{"key":"22_CR7","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/s00357-009-9041-0","volume":"26","author":"V. Chepoi","year":"2010","unstructured":"Chepoi, V., Fichet, B., Seston, M.: Seriation in the presence of errors: NP-hardness of l \u2009\u221e\u2009-fitting Robinson structures to dissimilarity matrices. J. Classification\u00a026, 279\u2013296 (2010)","journal-title":"J. Classification"},{"key":"#cr-split#-22_CR8.1","doi-asserted-by":"crossref","unstructured":"Chepoi, V., Seston, M.: Seriation in the presence of errors: A factor 16 approximation algorithm for l \u2009\u221e\u2009-fitting Robinson structures to distances. Algorithmica (2009);","DOI":"10.1007\/s00453-009-9319-y"},{"key":"#cr-split#-22_CR8.2","unstructured":"Available electronically"},{"key":"22_CR9","unstructured":"Van Bevern, R.: The Computational Hardness and Tractability of Restricted Seriation Problems on Inaccurate Data. Diplomarbeit. Institut f\u00fcr Informatik, Friedrich-Schiller-Universit\u00e4t, Jena, Germany (2010)"},{"key":"22_CR10","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/j.jcss.2009.07.001","volume":"76","author":"M. Dom","year":"2010","unstructured":"Dom, M., Guo, J., Niedermeier, R.: Approximation and fixed-parameter algorithms for consecutive ones submatrix problems. J.Comput. System Sci.\u00a076, 204\u2013221 (2010)","journal-title":"J.Comput. System Sci."},{"key":"22_CR11","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1007\/s00453-008-9233-8","volume":"57","author":"D. Marx","year":"2010","unstructured":"Marx, D.: Chordal deletion is fixed-parameter tractable. Algorithmica\u00a057, 747\u2013768 (2010)","journal-title":"Algorithmica"},{"key":"22_CR12","series-title":"LNCS","volume-title":"Proc.\u00a05th\u00a0IPEC","author":"Y. Villanger","year":"2010","unstructured":"Villanger, Y.: Proper interval vertex deletion. In: Proc.\u00a05th\u00a0IPEC. LNCS, Springer, Heidelberg (December 2010)"},{"key":"22_CR13","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","volume":"32","author":"B. Reed","year":"2004","unstructured":"Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Oper. Res. Lett.\u00a032, 299\u2013301 (2004)","journal-title":"Oper. Res. Lett."},{"key":"22_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-642-02094-0_4","volume-title":"Algorithmics of Large and Complex Networks","author":"J. Guo","year":"2009","unstructured":"Guo, J., Moser, H., Niedermeier, R.: Iterative compression for exactly solving NP-hard minimization problems. In: Lerner, J., Wagner, D., Zweig, K.A. (eds.) Algorithmics of Large and Complex Networks. LNCS, vol.\u00a05515, pp. 65\u201380. Springer, Heidelberg (2009)"},{"key":"22_CR15","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Comp. Sci.\u00a01, 237\u2013267 (1976)","journal-title":"Theor. Comp. Sci."},{"key":"22_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-642-03816-7_28","volume-title":"Mathematical Foundations of Computer Science 2009","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R., Guo, J., Moser, H., Niedermeier, R.: A complexity dichotomy for finding disjoint solutions of vertex deletion problems. In: Kr\u00e1lovi\u010d, R., Niwi\u0144ski, D. (eds.) MFCS 2009. LNCS, vol.\u00a05734, pp. 319\u2013330. Springer, Heidelberg (2009)"},{"key":"22_CR17","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/S0020-0190(03)00298-9","volume":"87","author":"B.S. Panda","year":"2003","unstructured":"Panda, B.S., Das, S.K.: A linear time recognition algorithm for proper interval graphs. Inf. Process. Lett.\u00a087, 153\u2013161 (2003)","journal-title":"Inf. Process. Lett."},{"key":"22_CR18","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1006\/jctb.1993.1052","volume":"59","author":"J.L. Fouquet","year":"1993","unstructured":"Fouquet, J.L.: A strengthening of Ben Rebea\u2019s lemma. J.\u00a0Combin. Theory Ser.\u00a0B\u00a059, 35\u201340 (1993)","journal-title":"J.\u00a0Combin. Theory Ser.\u00a0B"},{"key":"22_CR19","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol.\u00a0A. Springer, Heidelberg (2003)"},{"key":"22_CR20","series-title":"LNCS","first-page":"17","volume-title":"Proc.\u00a04th\u00a0IWPEC","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L.: Kernelization: New upper and lower bound techniques. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2008. LNCS, vol.\u00a05917, pp. 17\u201337. Springer, Heidelberg (2009)"},{"key":"22_CR21","doi-asserted-by":"publisher","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\u00a038, 31\u201345 (2007)","journal-title":"ACM SIGACT News"}],"container-title":["Lecture Notes in Computer Science","Graph Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16926-7_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T01:06:00Z","timestamp":1559783160000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16926-7_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642169250","9783642169267"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16926-7_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}