{"entities":{"Q1210553":{"pageid":1221302,"ns":120,"title":"Item:Q1210553","lastrevid":42947389,"modified":"2025-07-16T07:19:19Z","type":"item","id":"Q1210553","labels":{"en":{"language":"en","value":"Paths in interval graphs and circular arc graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 179588"}},"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":"Q1210553$9135FAED-F821-442B-9FFB-E061183B8055","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a717e34339e181ef081e4c6d572df8ea36bb1d4d","datavalue":{"value":{"text":"Paths in interval graphs and circular arc graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1210553$33337F9A-EF65-4C02-80C1-FAA91E630D15","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e496f87ba83bd1f4195beeb860cd77ef05b247ef","datavalue":{"value":"0777.05081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1210553$8D7AA14D-EE3F-4AE9-B649-FB1B1C650490","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d3523fbede1e04eeedc31df05e2833013a4b9c5d","datavalue":{"value":"10.1016/0012-365X(93)90223-G","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1210553$85757470-D0DE-4CA1-860A-63DCB4959282","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"efc35cf3e0639840fea360bd5e9b46c46abc9a77","datavalue":{"value":{"entity-type":"item","numeric-id":169283,"id":"Q169283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210553$289D43CC-DB76-40EE-BAB6-F1F887FDC958","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210553$C4F4AC51-62DC-4AC0-BD3E-CB3328D8E5B1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ca925aef735ee73d86c6a323015bc1282d85f7d8","datavalue":{"value":{"time":"+1993-08-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1210553$D788B0BD-21B9-44A2-98F2-B0992F00A535","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b314ceb1bdbcdf7c205db40df3d51dcb80ef4f4b","datavalue":{"value":"Interval graphs and circular arc graphs are intersection graphs of intervals on a line resp. of arcs on a circle. We give polynomial-time algorithms for several path cover problems in such graphs, e.g. for finding a Hamiltonian path in a circular arc graph. Some seemingly similar problems remain open here: Can one find in polynomial time (1) a Hamiltonian cycle in a circular arc graph, (2) a Hamiltonian path with prescribed start vertex in an interval graph?","type":"string"},"datatype":"string"},"type":"statement","id":"Q1210553$28698DDE-B276-49E3-AEF6-022E53C1C0EC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1210553$2B6632D1-3CB0-46F5-9BF1-59E022AAC1B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1210553$9377C28F-49E2-4EA3-B75D-E34525F34E6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1210553$FBAB494B-04AC-43CD-986E-AA8924B67BE6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"01ed38504d3adccd0582280935783c9234b5d3db","datavalue":{"value":"179588","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1210553$A4AC02D7-5362-4AF2-844F-B726E44D3330","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"86be7556738e9e4e480945c864a01e3fc0318ce4","datavalue":{"value":"circular arc graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1210553$523DFEB0-4223-4389-A7C8-B70FC8FB3D25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25f8eba8c9d529f212c848e074f37e4d66acf3cf","datavalue":{"value":"intersection graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1210553$FE44CD3E-0C73-4E06-BF87-087DD3C72899","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a92166f5adeebffc8c81c6abb980ed495030be8","datavalue":{"value":"polynomial-time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1210553$2411BA6F-AA9C-474F-A9E8-966D03B5FB66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e5bbd5bf2ad6684a967ea2236cdd3fda8dfd8d1","datavalue":{"value":"Hamiltonian path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1210553$5DFA4ECC-592B-42C7-B49B-BE24E62F7BB0","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":"Q1210553$AD17E024-0801-419F-8217-AB38EEC3D358","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"df54017c28e36c40158aae1756198436a7e36586","datavalue":{"value":{"entity-type":"item","numeric-id":1108807,"id":"Q1108807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210553$F08E2044-8B52-4CE7-AA5C-F9284E3C11F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb58559dbcbec2468b43206f2492cdb153b63a53","datavalue":{"value":{"entity-type":"item","numeric-id":1050117,"id":"Q1050117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210553$A2B36F0B-D942-40E6-ADCC-830C4EB473CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5945f050a45bd43d698004e6b0e2b06dd2fb562e","datavalue":{"value":{"entity-type":"item","numeric-id":1092669,"id":"Q1092669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210553$94E3500C-6789-48DC-9946-32431AFF0F9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac7f04bfc755103b505310e94b46f9d83558eff1","datavalue":{"value":{"entity-type":"item","numeric-id":1825646,"id":"Q1825646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210553$E3E6505F-51D6-4B1E-ABF7-9CE9B3B7D4FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ce3a94db921e6cba7ad432e9dc6feb40cc6db53","datavalue":{"value":{"entity-type":"item","numeric-id":1066921,"id":"Q1066921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210553$626733BE-A2F5-4906-BAEF-EBCFA8CD959E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9914f8121a32baf6895c6797ec99c63c32102968","datavalue":{"value":{"entity-type":"item","numeric-id":1242450,"id":"Q1242450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210553$7BBFF862-B1E6-46D2-965B-90AAED250C46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b02b4f48d0037fad08c849795b6a26429a780be","datavalue":{"value":{"entity-type":"item","numeric-id":1823687,"id":"Q1823687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210553$DC9267D4-F7D9-497F-892B-B173D6F1AAB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c409653b4a03b84fb9ab4a6c8d258974ecda1a72","datavalue":{"value":{"entity-type":"item","numeric-id":918703,"id":"Q918703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210553$78F36365-F01C-4E41-913F-DFCDC8175AF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210553$B3C77636-A2AC-4AEE-8B01-EBE2F1DC8D1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c17b1143dff0bc685088f8d62dbc046a1f96e02e","datavalue":{"value":{"entity-type":"item","numeric-id":5732670,"id":"Q5732670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210553$39ABDD8B-7F84-43AB-B4E1-B7FEA104D81B","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":"Q1210553$90B5F435-421F-4EA5-B00B-49D5D2C17A8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc1236a6b7e888ea271edc7a134a09ce07c03dec","datavalue":{"value":{"entity-type":"item","numeric-id":1060229,"id":"Q1060229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210553$19C547EB-A6E2-42A3-A0E5-D2DAEDDC19BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db0285625f074a48cd1908122f2f7d851fdd299e","datavalue":{"value":{"entity-type":"item","numeric-id":3747723,"id":"Q3747723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210553$B9648FAD-EC07-4AFD-AE8A-88254DAC5214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23fddf78676d43f688f22d0ab9603f5b22b0a030","datavalue":{"value":{"entity-type":"item","numeric-id":1066674,"id":"Q1066674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210553$52008411-1CCA-47AF-8BCC-E3134F92337E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c56d57ecea35b3aa6cc1812712734715cb7061f6","datavalue":{"value":{"entity-type":"item","numeric-id":1186160,"id":"Q1186160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210553$A5333244-967B-4C23-B21B-672340E026A9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27bfb14b7a0f87efd9278d9a1cdffa844259ea67","datavalue":{"value":{"entity-type":"item","numeric-id":4810505,"id":"Q4810505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3fcecac24aed54bd2d5e67a8318a3f1f43f7408","datavalue":{"value":{"amount":"+0.9289887","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1210553$5C55685A-1EDA-4FB6-9E31-6488B7F6D5EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d925fabf1e30c12dacc0ac001c53eb795f75224a","datavalue":{"value":{"entity-type":"item","numeric-id":4698084,"id":"Q4698084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6d3a8452c22099fc2701f5d2cb83a617de7e2cb","datavalue":{"value":{"amount":"+0.92256624","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1210553$07270C7A-BD84-4300-811B-9A3CEC6D4A71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"115334db6aedec9b6b2e0984f28369e119219023","datavalue":{"value":{"entity-type":"item","numeric-id":3508573,"id":"Q3508573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73246dffd9f02ba1d34651917a20a63f1e09252d","datavalue":{"value":{"amount":"+0.92197645","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1210553$8F37A003-5BCC-4F5C-96E7-1249D68C9A6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f0c450554a77ffd321ecaf8c2411e66041fe340","datavalue":{"value":{"entity-type":"item","numeric-id":2416437,"id":"Q2416437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7230010bb8b6e1e2c7f0d4c3fe4e3debd1a753ea","datavalue":{"value":{"amount":"+0.918823","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1210553$88FEF700-3C9E-4F4D-805A-EDCB5C81ED05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa7f594d4866369e254062e757de290fc31e8fca","datavalue":{"value":{"entity-type":"item","numeric-id":2357159,"id":"Q2357159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6351231ead371b194e3929da922cd836896f898","datavalue":{"value":{"amount":"+0.9136256","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1210553$3D321539-EC6A-4215-AEB7-CE5990553B19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a381a00971f43d3552c0cead1e67575518f5458a","datavalue":{"value":{"entity-type":"item","numeric-id":4819244,"id":"Q4819244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b83d12805cbf856de7d8dc19103c803f8cde98a3","datavalue":{"value":{"amount":"+0.90378034","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1210553$02D39A3A-C612-4239-8506-2FC9387EDE93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"354b73840fa6f21558adee6a5e1161f216a6b64f","datavalue":{"value":{"entity-type":"item","numeric-id":940975,"id":"Q940975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79a75bd2f38e0bdca4b181d8c3bd81afa7922bca","datavalue":{"value":{"amount":"+0.9017891","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1210553$47D1023E-EF8F-4E32-9648-3102B9567632","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20571f34048ab69dcdc987de451f9d6dd0dfff4f","datavalue":{"value":{"entity-type":"item","numeric-id":2516667,"id":"Q2516667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03fe11f3c1b838554b928746c560220b34ad0567","datavalue":{"value":{"amount":"+0.89830697","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1210553$29F69A1F-7DCC-4024-B9D1-AFFB53D03C7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"171b2f77e62cdc030428ae2c8db9f8234088be31","datavalue":{"value":{"entity-type":"item","numeric-id":4780288,"id":"Q4780288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bed3af2a376d2e59143be1d9ec9a0dde5438f6d9","datavalue":{"value":{"amount":"+0.89795005","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1210553$7C76D43E-CAE5-47D1-8587-F6A3A0973E66","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1210553","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1210553"}}}}}