{"entities":{"Q477637":{"pageid":479404,"ns":120,"title":"Item:Q477637","lastrevid":62165295,"modified":"2026-04-11T04:12:45Z","type":"item","id":"Q477637","labels":{"en":{"language":"en","value":"The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6378661"}},"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":"Q477637$1323A0CE-8C35-411B-AF24-BCE5FCCBDDB2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"61817798203272ac68697ac9591cd68706cc70d0","datavalue":{"value":{"text":"The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q477637$E74311EA-343C-453F-B09A-20D74BE49A57","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4c143a1ca7353d640eb35439ff75a6b07cf6b32a","datavalue":{"value":"1304.05045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q477637$1241A20F-09F5-4484-8523-A0D53A6C646F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6e77dc62432e0084fdda4e3c056dc8f26060354d","datavalue":{"value":{"entity-type":"item","numeric-id":186209,"id":"Q186209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q477637$AEC2B88A-16C6-4B6F-9843-1B416D566BB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8d57ceebca14f4945cbb196f18cb09249ac8d15b","datavalue":{"value":{"entity-type":"item","numeric-id":281766,"id":"Q281766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q477637$1B6AD7CB-BED3-4C3D-9AA0-863D77F3F667","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q477637$77C32EB9-D09B-4F69-88C6-3084FFF60963","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"647b7a1b0f81a95dd0d55b044a22a9b52645ffc6","datavalue":{"value":{"time":"+2014-12-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q477637$B479FC2B-204A-45E3-8BCE-E78F120A1630","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q477637$B8952862-4590-4833-ADF6-CA748CA61D53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"245985807b016d115d4f4ba6c61b278b3497fcff","datavalue":{"value":"05C07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q477637$4CB5F8EE-50BF-4B81-8CAB-9329D512C2C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q477637$1A0ABE86-1CC5-4184-9F48-64B88488611F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q477637$BCF9D8F0-B413-4106-BE0D-D24AEA50104D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c7e4b3b02b8e8185d2645c7ee7a0fb4a49f251aa","datavalue":{"value":"6378661","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q477637$F94EAC0C-93F4-48CB-9300-99DFE07C399F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1787eabd5992604d274d22afb57851489655834","datavalue":{"value":"bounded-degree graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q477637$A10F3571-AF0C-4905-B556-13B8E6D1B491","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6f84219d6ee3ac675a4b4e05a3ba126c6aff0196","datavalue":{"value":"backbone chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q477637$A68A456E-B43D-41D6-B687-D5E3A0FCF85D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed3b495ba8c3c3bf5babb1d3213a6c0bf58078e5","datavalue":{"value":"graph algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q477637$502017B6-9C1A-4593-9858-3F7050EECF75","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":"Q477637$A56E7170-2F3D-4238-9462-E1D090D873A9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"aceb64844a62adc925c497ffa7eb0a30819f28b1","datavalue":{"value":"https://doi.org/10.1016/j.ipl.2014.09.018","type":"string"},"datatype":"url"},"type":"statement","id":"Q477637$0BA76714-CBF1-4144-83CF-9B5B5FD28036","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f2c0e45ea43d3c64741e11a926ac40076b1297b0","datavalue":{"value":"W2045373821","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q477637$DBB14189-139C-4131-A60A-CE352A5FEA07","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"40840e6c33125ba125a22a33fc62bee99a723d14","datavalue":{"value":{"entity-type":"item","numeric-id":5491719,"id":"Q5491719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q477637$62AF6E9A-03AD-4F4D-B28E-159E16ED83F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"014defb468e9a9d3888048651d8dd40bad740f2b","datavalue":{"value":{"entity-type":"item","numeric-id":5448772,"id":"Q5448772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q477637$962448A3-4CB4-40E0-8879-8F05648002E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"819abfe0a0e5be0d9a7bd2448759775336b2faab","datavalue":{"value":{"entity-type":"item","numeric-id":3445508,"id":"Q3445508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q477637$6A6777C9-F7A7-4D21-A250-57CD0839F186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"039e41ed6d8d403f872172c378176f3b68e0c083","datavalue":{"value":{"entity-type":"item","numeric-id":1045046,"id":"Q1045046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q477637$7EE51C1B-1F86-426B-89AD-24C730BBC579","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q477637$F7A6C8E3-8534-4DAC-B16D-1778130015A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20545941596176f69193cc216dadf5e35ac99bd2","datavalue":{"value":{"entity-type":"item","numeric-id":497343,"id":"Q497343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q477637$C5A83BB6-7377-4A26-BDE7-8B81C804D6A3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"89aa862c9a0771618a82ab872f957d17982891f5","datavalue":{"value":"10.1016/J.IPL.2014.09.018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q477637$AC752593-7507-4F14-88C1-5C4D39C3375D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41087c15f21c6e0152adf7f531c5fc4b65b96cee","datavalue":{"value":{"entity-type":"item","numeric-id":2341776,"id":"Q2341776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"547095f3a1a2c0128cdb40e5ed15ea39a42282ae","datavalue":{"value":{"amount":"+0.9050484299659728","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":"Q477637$9336A511-9FF7-46CF-BEB4-160143F32774","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85c160953e003891c02d9b91363abc617b94c618","datavalue":{"value":{"entity-type":"item","numeric-id":3517250,"id":"Q3517250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc1bb3e11377ae3d4628e9758e594c7893b7e80b","datavalue":{"value":{"amount":"+0.9049980044364928","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":"Q477637$0769AD75-D151-4B47-9037-74FC09687B55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d6348d85d07ed2947224019b53d508c4d2ff5a6","datavalue":{"value":{"entity-type":"item","numeric-id":3445508,"id":"Q3445508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19aac74e422312bde55f4505b2eee64bb66d9b8b","datavalue":{"value":{"amount":"+0.8865128755569458","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":"Q477637$08CDD474-EEFC-4835-B780-500438E65C18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9ba65bcfc30f8f5986e6ff7ac23315ce733efc5","datavalue":{"value":{"entity-type":"item","numeric-id":5902516,"id":"Q5902516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b202b2f5432e8ce1263dd0c4c1d46f9c71aa097","datavalue":{"value":{"amount":"+0.8670285940170288","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":"Q477637$D323DA5B-2194-492B-A371-8A06EF049713","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5eb1a02024644787078c58fafccd8c30a05b5b66","datavalue":{"value":{"entity-type":"item","numeric-id":968172,"id":"Q968172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f3c94a1084f55a60a191c8c4d0989dfa61228cc","datavalue":{"value":{"amount":"+0.8596834540367126","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":"Q477637$AB15AFAE-93A8-4AA5-9D68-4B3058413412","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_computational_complexity_of_the_backbone_coloring_problem_for_bounded-degree_graphs_with_connected_backbones"}}}}}