{"entities":{"Q686255":{"pageid":688104,"ns":120,"title":"Item:Q686255","lastrevid":63608724,"modified":"2026-04-11T14:19:40Z","type":"item","id":"Q686255","labels":{"en":{"language":"en","value":"Bounded discrete representations of interval orders"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 428110"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686255$84E321F2-0870-4E22-8774-B3219E001816","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"53188d896ec01bd41bb84d52761430e040999962","datavalue":{"value":{"text":"Bounded discrete representations of interval orders","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q686255$F9858848-61AE-48CC-9374-AE7B8AAA8788","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7ceff52a1fe01715ac860a85fb34d331ae797ce2","datavalue":{"value":"0787.06003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686255$EA773F23-4DC4-4B60-8CE5-26956846FF42","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"eb2176563a056df67859925c1c552d75e32ae79c","datavalue":{"value":"10.1016/0166-218X(93)90229-H","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686255$0DCED395-DD71-4801-AFD4-B540BCFEFF07","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f4646798f2e971edbee19143fd6e0c48a835b7f3","datavalue":{"value":{"entity-type":"item","numeric-id":442226,"id":"Q442226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686255$8C7449E1-294B-4838-ADF7-94257FEBFD0C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686255$DD1F6394-412E-4F11-A1A0-FED7B747576B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7a2ae337094f9b29ef7d03c29f436d8f988b84f0","datavalue":{"value":{"time":"+1994-05-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q686255$58445A94-62EA-4E9D-8282-12EA66F4D17F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1388e1c21c9543184a6881fd683313dd29a8f117","datavalue":{"value":"Given a finite interval order \\((A,>)\\) and \\(\\alpha,\\beta: A\\to\\mathbb{N}\\) non- negative integer constraints, an \\([\\alpha,\\beta]\\) bounded discrete representation of \\((A,>)\\) is a closed interval representation \\({\\mathcal J}: A\\to \\{[\\ell,r]\\mid \\ell,r\\in\\mathbb{Z}\\}\\) so that \\({\\mathcal J}(a_ i)={\\mathcal J}(i)= [\\ell_ i,r_ i]\\) with (a) \\(j>j \\iff \\ell_ i> r_ j\\) and (b) \\(\\alpha(i)\\geq r_ i-\\ell_ i\\geq \\beta(i)\\) for all \\(i\\in A\\), with \\({\\mathcal D}[\\alpha,\\beta]\\) denoting the collection of all finite interval orders permitting bounded discrete representations while \\({\\mathcal F}[\\alpha,\\beta]\\) consists of those interval orders not in \\({\\mathcal D}[\\alpha,\\beta]\\) having the property that all proper suborders \\(A'\\) of \\(A\\) are in \\({\\mathcal D}[\\alpha,\\beta]\\).   In this very useful paper, the author obtains a variety of interesting results by studying a directed graph \\(D(A,>,\\alpha,\\beta)\\) and its flow properties via the vertex-incidence matrix \\(M\\) of this graph and its relationships to these properties in terms of associated linear algebra, as expressed in Farkas' Lemma for example. The graph \\(D(A,>,\\alpha,\\beta)\\) is bipartite with vertices \\(L\\cup R=\\{\\ell_ 1, \\dots,\\ell_{| A|}\\}\\cup \\{r_ 1,\\dots, r_{| A|}\\}\\) and arcs \\(U\\cup V\\cup W\\cup Z\\) with lengths (weights) \\(U=\\{(\\ell_ i,r_ i)\\): \\(i=1,\\dots,| A|\\}\\) lengths \\(\\alpha(i)\\), \\(V=\\{(r_ i,\\ell_ i)\\}\\) lengths \\(-\\beta(i)\\), \\(W=\\{(\\ell_ i,r_ j)\\): \\(i>j\\}\\) lengths \\(-1\\), \\(Z=\\{(r_ j,\\ell_ i)\\): \\(i\\) and \\(j\\) equal or incomparable\\} lengths 0. A key idea involved is that of a negative cycle, i.e., a cycle of negative length in that \\((A,>)\\in {\\mathcal D}[\\alpha,\\beta]\\) iff \\(D(A,\\geq,\\alpha,\\beta)\\) contains no negative cycles. Based on this approach the author is able to provide a polynomial time decision algorithm for membership in \\({\\mathcal D}[\\alpha,\\beta]\\) as well as further properties of \\({\\mathcal F}[\\alpha,0]\\) (finite) and \\({\\mathcal F}[\\alpha,1]\\) (infinite if \\(\\alpha\\geq 2)\\). In the latter cases properties of negative cycles in graphs \\(D(A,>,\\alpha,0)\\) and \\(D(A,>,\\alpha,\\beta)\\) are important.","type":"string"},"datatype":"string"},"type":"statement","id":"Q686255$D0296E01-1AE0-4BFD-B15F-164610157B61","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f3d0b1de78ad0e32d646815f9dc7561538cada7","datavalue":{"value":"06A07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686255$FB3460D6-CB74-4BCC-9CFB-622CE76715E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686255$B2DCF281-7AD4-4700-9906-C873772C3DDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686255$45322531-BCE5-4E22-A74C-D9F3DBFBBC09","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b3f3b081cb0d9ae9b09c2adfb7b8dc55289e1f6f","datavalue":{"value":"428110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686255$5DD6F041-1E16-424A-B3FF-52D1A4BE706D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6815092d648b11f6c8061071bd3b07ffb4ff9fda","datavalue":{"value":"finite interval order","type":"string"},"datatype":"string"},"type":"statement","id":"Q686255$E1F5EF2F-DF62-4243-ABD1-7C04F950F58E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"02aaced2d36e29fa3c0b1d52732bdb270e85758b","datavalue":{"value":"bounded discrete representation","type":"string"},"datatype":"string"},"type":"statement","id":"Q686255$0E483915-C6F1-495A-9E58-7C0E1F321D83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b30424142393c2fad52d0eb069a3b1460e7b8ac3","datavalue":{"value":"closed interval representation","type":"string"},"datatype":"string"},"type":"statement","id":"Q686255$CA943438-E536-4E55-B22C-9B0A02123B12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6bf023653318cc5b8c727563611596d2cf1a818a","datavalue":{"value":"directed graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q686255$B9E132D4-6587-46C4-80D9-C75C04CC7B37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dcee6f7a74fc73c60f3deb8d985df5711d97464a","datavalue":{"value":"flow","type":"string"},"datatype":"string"},"type":"statement","id":"Q686255$0633BE9B-A3F9-4D50-A238-7FAB2616E501","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f9e4367caa174b6d07c58bcd1dc9d341d8fafd7","datavalue":{"value":"vertex-incidence matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q686255$CF2DBDF5-0E02-4CAB-A55B-E6FE63F121DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"634a3bf930c9b4278d1419ddf44fc648417e2dfc","datavalue":{"value":"associated linear algebra","type":"string"},"datatype":"string"},"type":"statement","id":"Q686255$DC2A7140-11DF-4E6F-AE5D-61B96E86BEEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0bcee84969a6eb7bd62da9158e27e083bc13f1b2","datavalue":{"value":"Farkas' Lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q686255$32589299-CBB3-437F-8196-FFAA9D2582A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b62c6148b19dfaf55b4921e256ed9df7c54c5b6","datavalue":{"value":"negative cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q686255$210A53C1-E51E-446A-9612-AA5BA8AD1055","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f82bd16582e181cdbb84f6e0971dc8c31c38a659","datavalue":{"value":"polynomial time decision algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q686255$6AD6E72E-C22D-4F57-9862-396B94FFF120","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b626688718ca3d61fce8479b1c17fa40d92d8dda","datavalue":{"value":{"entity-type":"item","numeric-id":233347,"id":"Q233347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686255$FF6A5E88-F2CF-41DE-B623-53F89D8BB7B7","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686255$15145580-5909-4E33-BDD6-1496D41CE591","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea40651a0496c388a998528c9d0e97fcc3557aa4","datavalue":{"value":{"entity-type":"item","numeric-id":3325774,"id":"Q3325774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686255$AE7CAA16-AA05-4620-8D2E-9BFDCC9E651B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed2cf1e3c5cf3c763e86c2665ddd5288c764294b","datavalue":{"value":{"entity-type":"item","numeric-id":2546051,"id":"Q2546051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686255$72985D5F-D2A2-49D8-ABA7-35AD75DE1D05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bce677a9c061b16210c3b75fe5d9808dd9ed326","datavalue":{"value":{"entity-type":"item","numeric-id":1060230,"id":"Q1060230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686255$E8FC56E2-C5CF-41E3-8DF2-A8163FA7DEE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3ab86c5c12697815de915add32e504c8290e76b","datavalue":{"value":{"entity-type":"item","numeric-id":3816112,"id":"Q3816112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686255$B54EAF5F-A7EC-4988-9181-033B8514914A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686255$690C0646-65B9-4CEB-A52B-6250C3EEF3BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08736496fad7f1ee1630e83b4f57fe1861c09098","datavalue":{"value":{"entity-type":"item","numeric-id":3048571,"id":"Q3048571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686255$92ACF4ED-B974-4148-AC31-71D1AC80AE39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56c6c299e15ddeb001671e573dc9a5439e5a86a0","datavalue":{"value":{"entity-type":"item","numeric-id":3818127,"id":"Q3818127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686255$FC85FC3E-0C41-411F-9765-354B9D011796","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ce5f41c1478faf9a5829eb2b63b516e4eaf3dd0a","datavalue":{"value":"https://doi.org/10.1016/0166-218x(93)90229-h","type":"string"},"datatype":"url"},"type":"statement","id":"Q686255$98607007-5E42-45B3-97DD-6BF3C486CFC2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"425828d70b6ea1b780005775069b2334138f77ae","datavalue":{"value":"W1969070807","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686255$F3C7A887-0237-4881-8E13-71747753F70D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39f21d5b1caf2026ed3486019c0cdd06bb1b5732","datavalue":{"value":{"entity-type":"item","numeric-id":3626683,"id":"Q3626683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa53f89a94bbae5afe6904596f954545b1bffb8f","datavalue":{"value":{"amount":"+0.8461044430732727","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686255$ACD565DE-DAB7-4F56-A116-743271341B00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d24c0de91c8c3aacce6b8a571f9c00433791197","datavalue":{"value":{"entity-type":"item","numeric-id":4858946,"id":"Q4858946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a38c73084cb0d000412e248d9137224e4e7eda9","datavalue":{"value":{"amount":"+0.8210899233818054","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686255$473FE7E0-B8BC-4D9F-B5B3-993FBEA5C660","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5904b7ad7b5b568e741ae5d608486e0d6339b415","datavalue":{"value":{"entity-type":"item","numeric-id":4345419,"id":"Q4345419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cad6ea6d060941b6d52e57ea19e98f4d91ea61c","datavalue":{"value":{"amount":"+0.7898672819137573","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686255$BA0522BF-0E8F-4155-A7EA-1ACF427D2C81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a74ee8a5523efcbdd388d83ff17cfa78a3b0cfcd","datavalue":{"value":{"entity-type":"item","numeric-id":2497527,"id":"Q2497527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0b4eaf1212e7dd96070f76806225f783f3c8a5d","datavalue":{"value":{"amount":"+0.7888374328613281","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686255$F2E5F577-612E-4ACF-86E8-15D73E90C789","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"256021682943b5ba8b8f54b8247092622daadbd8","datavalue":{"value":{"entity-type":"item","numeric-id":1060230,"id":"Q1060230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2610ab23f95ad38c5adf2249984d2d386e481b8","datavalue":{"value":{"amount":"+0.7845134735107422","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686255$AB49B162-63D2-4BB1-AB0D-E4FB5AFDC85C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bounded discrete representations of interval orders","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bounded_discrete_representations_of_interval_orders"}}}}}