{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:12:54Z","timestamp":1725664374225},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540615767"},{"type":"electronic","value":"9783540706274"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61576-8_97","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:58:19Z","timestamp":1330275499000},"page":"378-395","source":"Crossref","is-referenced-by-count":0,"title":["Threshold graphs and synchronization protocols"],"prefix":"10.1007","author":[{"given":"Rossella","family":"Petreschi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea","family":"Sterbini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"Eisenberg M. A. and McGuire M. R. Further comments on Dijkstra's concurrent programming control problem. Comm. ACM, 15(11), 1972.","DOI":"10.1145\/355606.361895"},{"key":"31_CR2","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/S0167-5060(08)70731-3","volume":"1","author":"V. Chv\u00e1tal","year":"1977","unstructured":"V. Chv\u00e1tal and P. L. Hammer. Aggregation of inequalities in integer programming. Ann. Disc. Math., 1:145\u2013162, 1977.","journal-title":"Ann. Disc. Math."},{"issue":"2","key":"31_CR3","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1142\/S0129054190000102","volume":"1","author":"S. Agostino De","year":"1990","unstructured":"S. De Agostino and R. Petreschi. Parallel recognition algorithms for graphs with restricted neighbourhoods. Int. J. of Foundations of Comp. Sci., 1(2):123\u2013130, 1990.","journal-title":"Int. J. of Foundations of Comp. Sci."},{"issue":"1","key":"31_CR4","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1142\/S0129054192000036","volume":"3","author":"S. Agostino De","year":"1992","unstructured":"S. De Agostino and R. Petreschi. On PVchunk operations and matrogenic graphs. Int. J. of Foundations of Comp. Sci., 3(1):11\u201320, 1992.","journal-title":"Int. J. of Foundations of Comp. Sci."},{"key":"31_CR5","volume-title":"Programming Languages","author":"E. W. Dijkstra","year":"1968","unstructured":"E. W. Dijkstra. Cooperating sequential processes. In F. Genuys, editor, Programming Languages. Academic Press, New York, 1968."},{"key":"31_CR6","doi-asserted-by":"crossref","unstructured":"Burns J. E. Symmetry in systems of asynchronous processes. In Proc. 22nd Annual Symp. on Foundations of Computer Science, pages 164\u2013174, 1981.","DOI":"10.1109\/SFCS.1981.42"},{"issue":"5","key":"31_CR7","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/355592.365595","volume":"9","author":"D. E. Knuth","year":"1966","unstructured":"Knuth D. E. Additional comments on a problem in concurrent programming control. Comm. ACM, 9(5):321\u2013322, 1966.","journal-title":"Comm. ACM"},{"key":"31_CR8","volume-title":"Interval Orders and Interval Graphs","author":"P. C. Fishburn","year":"1985","unstructured":"P. C. Fishburn. Interval Orders and Interval Graphs. Wiley, New York, 1985."},{"key":"31_CR9","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1016\/0022-2496(70)90062-3","volume":"7","author":"P. C. Fishburn","year":"70","unstructured":"P. C. Fishburn. Intransitive indifference with unequal indifference intervals. Journal of Math. Psych., 7:144\u2013149, 70.","journal-title":"Journal of Math. Psych."},{"key":"31_CR10","first-page":"331","volume":"18","author":"S. F\u00f6ldes","year":"1978","unstructured":"S. F\u00f6ldes and P. L. Hammer. On a class of matroid-producing graphs. Colloq. Math. Soc. J. Bolyai (Combinatorics), 18:331\u2013352, 1978.","journal-title":"Colloq. Math. Soc. J. Bolyai (Combinatorics)"},{"issue":"3","key":"31_CR11","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1145\/363162.363167","volume":"10","author":"J. G. Bruijn De","year":"1967","unstructured":"De Bruijn J. G. Additional comments on a problem in concurrent programming control. Comm. ACM, 10(3):137\u2013138, 1967.","journal-title":"Comm. ACM"},{"key":"31_CR12","unstructured":"Le Lann G. Distributed systems, towards a formal approach. In IFIP Congress, pages 155\u2013160, 1977."},{"issue":"1","key":"31_CR13","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/358527.358537","volume":"24","author":"G. Ricart","year":"1981","unstructured":"Ricart G. and Agrawala A. K. An optimal algorithm for mutual exclusion in computer networks. Comm. ACM, 24(1):9\u201317, 1981. Corrigendum in Comm. ACM, 24 (9).","journal-title":"Comm. ACM"},{"issue":"2","key":"31_CR14","first-page":"147","volume":"26","author":"G. Ricart","year":"1983","unstructured":"Ricart G. and Agrawala A. K. Author's response to \u2018on mutual exclusion in computer networks\u2019 by carvalho and roucariol. Comm. ACM, 26(2):147\u2013148, 1983.","journal-title":"Comm. ACM"},{"key":"31_CR15","volume-title":"Computers and intractability. A guide to the theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. W. H. Freeman and Co., San Francisco, 1979."},{"key":"31_CR16","doi-asserted-by":"crossref","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"P. C. Gilmore","year":"1964","unstructured":"P. C. Gilmore and A. J. Hoffman. A characterization of comparability graphs and of interval graphs. Canad. J. Math., 16:539\u2013548, 1964.","journal-title":"Canad. J. Math."},{"issue":"1","key":"31_CR17","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1137\/0206008","volume":"6","author":"P. B. Henderson","year":"1977","unstructured":"P. B. Henderson and Y. Zalkstein. A graph-theoretic characterization of the PVchunk class of synchronising primitives. SIAM J. Comput., 6(1):88\u2013108, 1977.","journal-title":"SIAM J. Comput."},{"key":"31_CR18","unstructured":"Suzuki I. and Kasami T. An optimality theory for mutual exclusion algorithms in computer networks. In Proc. of the 3rd Int. Conf. On Distributed Computing Systems, pages 365\u2013370, Miami, 1982."},{"key":"31_CR19","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/S0304-0208(08)73469-8","volume-title":"Studies on Graphs and Discrete Programming","author":"T. Ibaraki","year":"1981","unstructured":"T. Ibaraki and U. N. Peled. Sufficient conditions for graphs to have threshold number 2. In P. Hansen, editor, Studies on Graphs and Discrete Programming, pages 241\u2013268. Nort-Holland Publishing Company, Amsterdam, 1981."},{"issue":"8","key":"31_CR20","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1145\/361082.361093","volume":"17","author":"L. Lamport","year":"1974","unstructured":"Lamport L. A new solution of Dijkstra's concurrent programming problem. Comm. ACM, 17(8):453\u2013455, 1974.","journal-title":"Comm. ACM"},{"issue":"7","key":"31_CR21","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1145\/359545.359563","volume":"21","author":"L. Lamport","year":"1978","unstructured":"Lamport L. Time, clocks and the ordering of events in a distributed system. Comm. ACM, 21(7):558\u2013565, 1978.","journal-title":"Comm. ACM"},{"issue":"3","key":"31_CR22","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0020-0190(81)90106-X","volume":"12","author":"G. L. Peterson","year":"1981","unstructured":"Peterson G. L. Myths about the mutual exclusion problem. Inf. Proc. Lett., 12(3):115\u2013116, 1981.","journal-title":"Inf. Proc. Lett."},{"issue":"1","key":"31_CR23","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1145\/357195.357199","volume":"5","author":"G. L. Peterson","year":"1983","unstructured":"Peterson G. L. A new solution to Lamport's concurrent programming problem using shared variables. ACM Toplas, 5(1):56\u201365, 1983.","journal-title":"ACM Toplas"},{"key":"31_CR24","unstructured":"Tze-Heng Ma. On the thresold dimension 2 graphs, manuscript, September 1993."},{"key":"31_CR25","unstructured":"N. V. R. Mahadev and U. N. Peled. Threshold Graphs and Related Topics. Elsevier Publishers, 1995."},{"key":"31_CR26","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0012-365X(84)90023-2","volume":"51","author":"P. Marchioro","year":"1984","unstructured":"P. Marchioro, A. Morgana, R. Petreschi, and B. Simeone. Degree sequences of matrogenic graphs. Discrete Math., 51:47\u201361, 1984.","journal-title":"Discrete Math."},{"issue":"2","key":"31_CR27","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1145\/358024.940975","volume":"26","author":"O. Carvalho","year":"1983","unstructured":"Carvalho O. and Roucairol G. On mutual exclusion in computer networks. Comm. ACM, 26(2):146\u2013147, 1983.","journal-title":"Comm. ACM"},{"issue":"1","key":"31_CR28","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1137\/0218010","volume":"18","author":"E. T. Ordman","year":"1989","unstructured":"E. T. Ordman. Minimal threshold separators and memory requirements for synchronization. SIAM J. Comput., 18(1):152\u2013165, 1989.","journal-title":"SIAM J. Comput."},{"key":"31_CR29","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1016\/S0167-5060(08)70749-0","volume":"1","author":"J. Orlin","year":"1977","unstructured":"J. Orlin. The minimal integral separator of a threshold graph. Ann. Disc. Math., 1:415\u2013419, 1977.","journal-title":"Ann. Disc. Math."},{"key":"31_CR30","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0012-365X(77)90066-8","volume":"20","author":"U. N. Peled","year":"1977","unstructured":"U. N. Peled. Matroidal graphs. Discrete Math., 20:263\u2013286, 1977.","journal-title":"Discrete Math."},{"issue":"4","key":"31_CR31","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/0020-0190(81)90100-9","volume":"12","author":"E. C. R. Hehner","year":"1981","unstructured":"Hehner E. C. R. and Shyamasundar R. K. An implementation of P and V. Inf. Proc. Lett., 12(4):196\u2013198, 1981.","journal-title":"Inf. Proc. Lett."},{"key":"31_CR32","doi-asserted-by":"crossref","unstructured":"Thomas Raschle and Klaus Simon. Recognition of graphs with threshold dimension two. In The 27th Annual ACM Symposium on Theory of Computing, Las Vegas, NE, 1995.","DOI":"10.1145\/225058.225283"},{"key":"31_CR33","unstructured":"Thomas Raschle and Andrea Sterbini. 2-threshold graphs can be recognized in O(n3) time. Private communication."},{"key":"31_CR34","unstructured":"Michel Raynal. Algorithms for mutual exclusion. North Oxford Academic, 1986."},{"key":"31_CR35","unstructured":"Andrea Sterbini. 2-Thresholdness and its Implications: from the Synchronization with PV chunk to the Ibaraki-Peled Cojecture. PhD thesis, University of Rome \u201dLa Sapienza\u201d, 1994."},{"key":"31_CR36","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0020-0190(72)90035-X","volume":"1","author":"H. Vantilborgh","year":"1972","unstructured":"H. Vantilborgh and A. van Lamsweerde. On an extension of Dijkstra's semaphore primitives. Inform. Process. Lett., 1:181\u2013186, 1972.","journal-title":"Inform. Process. Lett."},{"key":"31_CR37","first-page":"43","volume-title":"Programming Languages","author":"E. W. Dijkstra","year":"1965","unstructured":"Dijkstra E. W. Co-operating sequential processes. In F. Genuys, editor, Programming Languages, pages 43\u2013112. Academic Press, New York, 1965."},{"issue":"11","key":"31_CR38","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1145\/361179.361202","volume":"17","author":"E. W. Dijkstra","year":"1974","unstructured":"Dijkstra E. W. Self-stabilizing systems in spite of distributed control. Comm. ACM, 17(11):643\u2013644, 1974.","journal-title":"Comm. ACM"},{"issue":"4","key":"31_CR39","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1016\/0020-0190(80)90141-6","volume":"10","author":"R. W. Doran","year":"1980","unstructured":"Doran R. W. and Thomas L. K. Variants of the software solution to mutual exclusion. Inf. Proc. Lett., 10(4):206\u2013208, 1980.","journal-title":"Inf. Proc. Lett."},{"key":"31_CR40","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/BF00288966","volume":"17","author":"J. L. W. Kessels","year":"1982","unstructured":"Kessels J. L. W. Arbitration without common modifiable variables. Acta Informatica, 17:135\u2013141, 1982.","journal-title":"Acta Informatica"},{"issue":"3","key":"31_CR41","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1137\/0603036","volume":"3","author":"M. Yannakakis","year":"1982","unstructured":"M. Yannakakis. The complexity of the partial order dimension problem. SIAM J. Algebraic Discrete Methods, 3(3):351\u2013358, 1982.","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"4","key":"31_CR42","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1093\/comjnl\/34.4.345","volume":"34","author":"K. Yue","year":"1991","unstructured":"K. Yue and R. T. Jacob. An efficient starvation-free semaphore solution for the graphical mutual exclusion problem. Comput. J., 34(4):345\u2013349, 1991.","journal-title":"Comput. J."}],"container-title":["Lecture Notes in Computer Science","Combinatorics and Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61576-8_97.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:08:04Z","timestamp":1605629284000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61576-8_97"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540615767","9783540706274"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/3-540-61576-8_97","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}