{"entities":{"Q1180838":{"pageid":1191587,"ns":120,"title":"Item:Q1180838","lastrevid":66779889,"modified":"2026-04-12T12:48:24Z","type":"item","id":"Q1180838","labels":{"en":{"language":"en","value":"A polyhedral approach to edge coloring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 30041"}},"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":"Q1180838$D879CB60-D9C1-47B1-BB0D-3167C957217F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e958c731ace095ba8c8273a26c4bfbe56fa64017","datavalue":{"value":{"text":"A polyhedral approach to edge coloring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1180838$D15A9A0E-793A-4DB0-9A77-6ABC8B2018DC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5d1e8b094ce3ce1dc53ff63ba4f0be93ae6298af","datavalue":{"value":"0754.90062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180838$9AB27177-294A-40D5-A62D-872DFB0E670C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1292fdfffb12c3eee9509692759f25c3b161d506","datavalue":{"value":"10.1016/0167-6377(91)90003-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180838$7B366F26-6B5E-48D5-B5D4-652B12A3564C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"44a15f75aca8c763af80efc1e8cd50523df037b8","datavalue":{"value":{"entity-type":"item","numeric-id":223531,"id":"Q223531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180838$0DD2E901-4041-4DB7-9F2B-7B9D68301B6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a1c26346d40b730bc09009d003fb3565eb0646e5","datavalue":{"value":{"entity-type":"item","numeric-id":163009,"id":"Q163009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180838$DB9053AC-FAD4-41E4-90B8-AC48A97046C7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180838$4F866130-FC19-409A-950B-01D44E9FE1F1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70844ffc4666eabac4e20376c648613dbe8620f7","datavalue":{"value":{"time":"+1992-06-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1180838$8BCFAB2E-F41D-4D53-BC9B-62A3EE8AB42D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c9dc78631e00525922cb4778ed699ec70204ea88","datavalue":{"value":"The edge coloring problem is formulated as an integer linear program of covering edges by matchings. For the NP-hard case of 3-regular graphs a linear programming relaxation with additional constraints is considered using column generation. The theory and the algorithm use the fact that the chromatic index is equal to 3 or 4. Computational experiments with randomly generated and some special graphs are presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180838$2C17FB8E-B32C-44B8-99D9-21C330059FBE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180838$6FAAED32-8B92-497A-B88C-D47DB44110EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180838$80CEE2ED-FA40-4A27-A245-7D1CC9F5C95C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180838$E979E9C1-6694-4247-BE2F-33D16B7E6B16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180838$B4EE3A83-FAA3-47E4-8732-FA8C926A9647","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180838$EBA9F952-BFCB-4DF8-9F18-F7068D8364C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180838$91E94AEB-C686-41C8-A414-3E782228F269","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d550400b67148ac150a943881fbd05e682ea56f5","datavalue":{"value":"90-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180838$EABD52AC-8EF1-4BB5-A8F8-33CE3A6D3C74","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6390eb9d9711752575946042b3e5893a54b7bc6c","datavalue":{"value":"30041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180838$B569DB0D-1EB2-43E1-B41E-82B8DAAF548A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5eebfabfbd15ba71a459be245ca8d5c079c6efb5","datavalue":{"value":"polyhedral approach","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180838$BF2410BB-4DA9-4605-B1BC-DF538AA24FF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a35970f6c9d25db8fd6157359f5f87a41735c25d","datavalue":{"value":"edge coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180838$D36C20E7-4880-4193-AF47-87D37E0AA0FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f5ff91603dbdb7107f914624235077ac5e1d02ce","datavalue":{"value":"covering edges by matchings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180838$D8AF1E87-BFD0-4EC4-B408-3BAEFDDF5F75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180838$73C1F3AA-3778-41F0-B319-A7C8ED6C5573","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6ca28fe262dc4406acfcbf757b519c703f60b86","datavalue":{"value":"3-regular graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180838$85F147B8-8389-4B05-A697-E617F243F44C","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"b58d1a3ee3251ef2e15a091d111ea82a95c281d0","datavalue":{"value":"Q56390700","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180838$88AAE24D-95C2-4797-A617-7798DB9D496C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"428db2522b86322eddab35ce9ee5f612b48777eb","datavalue":{"value":{"entity-type":"item","numeric-id":915655,"id":"Q915655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180838$1C2CEEAB-2B2B-435D-93F8-2B79CD5B7EEA","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":"Q1180838$D2449680-184F-4A19-9335-D910595817E9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f145cca5409c20a724e3c7d8dbe68860c3d69d6f","datavalue":{"value":"https://doi.org/10.1016/0167-6377(91)90003-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1180838$42BD7BB7-C998-4047-AF5E-8BBCAE31A99C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6bf6a95c40192da67921177d6af042df9bcc7403","datavalue":{"value":"W2163809252","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180838$6E5F9241-464C-40A4-87F1-81720DF4301E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b77d70b468b298dec116253d59890a02b5104a1","datavalue":{"value":{"entity-type":"item","numeric-id":3885518,"id":"Q3885518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180838$4FFEA976-0B5A-47E8-8C72-1BC60CC8F644","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bd8b848f40aaa3f56b8b15df38fbe662aeb1afa","datavalue":{"value":{"entity-type":"item","numeric-id":5516087,"id":"Q5516087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180838$0C27AFE5-448D-4E65-B2A0-3D226584B60D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5335f25c6d6f0cd75a359259eb867be7142f3d9d","datavalue":{"value":{"entity-type":"item","numeric-id":801928,"id":"Q801928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180838$042E3ABF-58B5-4FF7-8D51-7BC6A67BC814","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d1474ad965005531fc787ddda571bd10843eacd","datavalue":{"value":{"entity-type":"item","numeric-id":3853641,"id":"Q3853641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180838$12FD3E08-3F22-48D9-B3F4-4F9F9C59D5F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82fec6e580bc1a1c6b85af965d03783746bfb4ef","datavalue":{"value":{"entity-type":"item","numeric-id":3703653,"id":"Q3703653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180838$4623DD7F-C11D-4A8E-AEA5-91D28A5467D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ca8e2226bc49403f5d34bedd57297744e386790","datavalue":{"value":{"entity-type":"item","numeric-id":1168215,"id":"Q1168215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180838$FABD0D17-F18B-4F2B-9C63-DF077ED350E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631200adace0f14c2f6d92fc47cb2d9f5d82cdbb","datavalue":{"value":{"entity-type":"item","numeric-id":3928241,"id":"Q3928241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180838$D21FE93C-C0E0-4BD8-B750-18423D81ED1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180838$DB680825-91C2-4A8B-9F20-14B6A8060D41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4def438d8a28321802a44dbba53d7d9b373961a","datavalue":{"value":{"entity-type":"item","numeric-id":3923934,"id":"Q3923934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180838$65F59312-8564-4AF1-95E4-C470DA32E858","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4fa5c0efe0c39997534bb44636c6730a4e42c655","datavalue":{"value":{"entity-type":"item","numeric-id":3965907,"id":"Q3965907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180838$0575A3F2-A82F-4A37-B611-4634DDE5191D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e99da589d7100fee8c775ba840d0a2287dbe7cc7","datavalue":{"value":{"entity-type":"item","numeric-id":4198789,"id":"Q4198789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180838$ED55EA28-B1F6-4367-B086-670D7059BE28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82a95cd03b5cff5990fab382c5e862fff1a48912","datavalue":{"value":{"entity-type":"item","numeric-id":3208680,"id":"Q3208680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180838$54D63902-7716-41E1-AC8D-498C34485815","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b443d28d2cf5dc60e84dcdf32fa3ba89e6f4cbe","datavalue":{"value":{"entity-type":"item","numeric-id":4433446,"id":"Q4433446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bfae16e10a4c621ed70aa851831137b8c670aef2","datavalue":{"value":{"amount":"+0.8258980512619019","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":"Q1180838$56940871-BB1B-476E-9FC5-38EA6FC4961E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4d2c3a11a6e77abe476d4549ceaabfa1bb997dc","datavalue":{"value":{"entity-type":"item","numeric-id":688209,"id":"Q688209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c1044dcde83cb4542585d4d440b464721532af6","datavalue":{"value":{"amount":"+0.8106765151023865","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":"Q1180838$840FA80D-8098-4BC2-960D-BB2D0A3C911F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b283db389854c407fb618171a70b3f47beb8fe8e","datavalue":{"value":{"entity-type":"item","numeric-id":3503456,"id":"Q3503456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a7cd9049bd40880f49a1d5541d62b8d8b8b1ea5","datavalue":{"value":{"amount":"+0.8081075549125671","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":"Q1180838$C0AA9ABA-4972-4ADE-B2C2-E90BD583BD41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcbb3a1544a0231183b683f7c50891d36f391f72","datavalue":{"value":{"entity-type":"item","numeric-id":3725544,"id":"Q3725544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"169faab0ac4531ac079e9307924dd283e6bc2cb0","datavalue":{"value":{"amount":"+0.8054645657539368","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":"Q1180838$185DFB97-380F-45B5-A386-96EB157DA6DB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A polyhedral approach to edge coloring","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_polyhedral_approach_to_edge_coloring"}}}}}