{"entities":{"Q1923620":{"pageid":1934362,"ns":120,"title":"Item:Q1923620","lastrevid":46397445,"modified":"2025-12-24T17:09:05Z","type":"item","id":"Q1923620","labels":{"en":{"language":"en","value":"The parity path problem on some subclasses of perfect graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 933129"}},"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":"Q1923620$1EB01DEF-39FB-4F69-9241-2031F0C103CB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"801acdaa3467a856bb7aa1c0fc0aca8720284756","datavalue":{"value":{"text":"The parity path problem on some subclasses of perfect graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1923620$5971B6DA-FC81-42C8-A1DA-E7A328C2551F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"52de874e91c66723b1710d3d30dcdc994b001c9b","datavalue":{"value":"0859.05056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923620$EA9C13CD-D03A-4AF8-BD83-3C4772E18F69","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"845841ed50a272b587f77eff8b6d160dcbe83fc2","datavalue":{"value":"10.1016/0166-218X(95)00065-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923620$D17C7A9F-7008-49A9-8C93-A6489CD673AC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cabeb39dcf0dbe4c08c3808baa04002d1d09676b","datavalue":{"value":{"entity-type":"item","numeric-id":1923619,"id":"Q1923619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923620$FBD6E128-57C2-4BC4-9EE1-24937C37C459","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0e52a12d90ca5312fef7acb3a90e1100b17ed79f","datavalue":{"value":{"entity-type":"item","numeric-id":189690,"id":"Q189690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923620$8BB1EDDB-2F23-4F88-9AC5-6B9823338741","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":"Q1923620$8B794216-D010-4AE4-AD57-6A602C163194","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"987a2f2e82526aa2085dc97bf2e88574c6b234f8","datavalue":{"value":{"time":"+1997-04-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1923620$7F69C9BF-F9EC-453A-AB52-527D9BDB7B98","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3395a2cd6863e39784161d0f578415f36fc38e6f","datavalue":{"value":"http://www.elsevier.com/locate/dam","type":"string"},"datatype":"url"},"type":"statement","id":"Q1923620$302A45B5-52AD-468E-BFED-C89CA326CEE9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1d4cbdaba339808ee116ea84e75ede3009d1bed6","datavalue":{"value":"The parity path problem is the problem of finding two paths of different parity between two vertices. The problem is NP-complete on general graphs. In this paper, the authors consider the problem for comparability (i.e., transitively orientable), permutation, and cocomparability graphs. They give polynomial algorithms for these graphs by using the transitive orientability of the graphs to modify a breadth-first search.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923620$FCF00AD7-A51E-4786-ABAA-7781A076E6AA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bf8837edd6f8e1022b15c3d0748921656854f53e","datavalue":{"value":{"entity-type":"item","numeric-id":1811077,"id":"Q1811077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923620$1087A622-7BAC-4F5E-8FDD-EACD07575294","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923620$A77856E2-B151-4481-820F-7366EC7E638A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923620$480823A1-2110-46F5-8F56-CBB7C99ACE04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923620$8510A7FC-D106-4C2D-99CF-7F2B9FE0F3A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923620$023CDD80-E1F0-4910-8F81-3F3CE61F9CBC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"31a0a9ae9d3f9cb67ffdc2f923e2223cb33ba4be","datavalue":{"value":"933129","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923620$11E0AB4A-7AB6-4F99-995A-F874DBF10483","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5cba4f4e6b1d6add40394622cbe47bbb0afecf1c","datavalue":{"value":"permutation graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923620$FCD72BA8-B9B5-43D7-9D76-05F0FF10C6CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"907b39a9fd50efb160d0ed08ec5ae1a381469f07","datavalue":{"value":"parity path problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923620$771CDFF1-4B82-4DB0-ABE0-A08E756C76CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923620$FB07CBA1-5BE1-4E02-B143-5E6A0CAEA89A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1103045e8b9ffcb15329329abddd16e71a9fb5","datavalue":{"value":"comparability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923620$AF4C49AD-1F83-47BB-AB7E-13DF61BFBB72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cbfeffd12b664e76aec2f0d8ca9ba37ca2617ebb","datavalue":{"value":"cocomparability graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1923620$100650D1-0F5C-4C0C-9D30-FD97255A4963","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":"Q1923620$9F9EE0AF-8B97-4F66-B9CA-5E9A6556D67E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c5d85957a66c9405dfd75196371a5263c33da21","datavalue":{"value":{"entity-type":"item","numeric-id":802884,"id":"Q802884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923620$2F9FB0C7-0DAC-4387-AA88-6FAA04EF4E81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2122f250ea4d4b58a6010b834acd0da59c576b0","datavalue":{"value":{"entity-type":"item","numeric-id":686257,"id":"Q686257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923620$007CB58C-21FF-457C-BC64-B6FE6B7BC56B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8a74f042ba1f29a12a670ab9d659cf777707121","datavalue":{"value":{"entity-type":"item","numeric-id":798301,"id":"Q798301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923620$CD5B633A-0E75-45AC-850C-23F5BFC9BF9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d82cfa9f684c3350648874deb95288407da9381e","datavalue":{"value":{"entity-type":"item","numeric-id":1175980,"id":"Q1175980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923620$EC93FF90-CC6D-4839-9788-16DA4434C366","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":"Q1923620$A0FD64C5-8896-4360-AF5C-A26F2DC777E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"565e1c631f28f5626e28b4b72f070c887ee0b094","datavalue":{"value":{"entity-type":"item","numeric-id":3685215,"id":"Q3685215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1923620$FF02828F-CD65-4320-B2CA-CFEC14806443","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8c2571de6715bd99089e96d0d911cf9ccbc4d2f5","datavalue":{"value":"W1970625924","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1923620$513E7D40-BA29-4BE6-B3BE-6AC21F8FFAAB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a66e14b311543d0318df54bbd24b5ce0dbcf805","datavalue":{"value":{"entity-type":"item","numeric-id":1917257,"id":"Q1917257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d96f37bc33256424d917721c508a056035415012","datavalue":{"value":{"amount":"+0.863989531993866","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":"Q1923620$7F6E5FF6-A5CB-42F3-A7EC-8218E7811E92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee396aafba50c530fd089384ca3538b4587f05b4","datavalue":{"value":{"entity-type":"item","numeric-id":3222874,"id":"Q3222874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc53ea8aaec0cb38c17f8449d2f10b9c7363b432","datavalue":{"value":{"amount":"+0.8271523118019104","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":"Q1923620$BC7C8674-75B7-4F7C-84D7-092BB016B97B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d231b4752fb704262314300ea21c163e96ed219","datavalue":{"value":{"entity-type":"item","numeric-id":5743428,"id":"Q5743428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4b32044f75fb701a9926bed5faedb8f7b70a89f","datavalue":{"value":{"amount":"+0.8047932386398315","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":"Q1923620$A471F0DE-BD7F-4966-A87E-C67FC845AC35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91bb1804ba5d58de869bad53d69666b757c5f7ca","datavalue":{"value":{"entity-type":"item","numeric-id":3345793,"id":"Q3345793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d149fd17f8c08fce51cc16d49b24876e61463272","datavalue":{"value":{"amount":"+0.7970754504203796","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":"Q1923620$889B7703-4F0C-44EE-956A-CEFA71A25C94","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1923620","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1923620"}}}}}