{"entities":{"Q1578404":{"pageid":1589144,"ns":120,"title":"Item:Q1578404","lastrevid":47009547,"modified":"2025-12-26T01:15:35Z","type":"item","id":"Q1578404","labels":{"en":{"language":"en","value":"A linear algorithm for finding \\([g,f]\\)-colorings of partial \\(k\\)-trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1496843"}},"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":"Q1578404$E23ECBC9-41C5-4E3C-82F4-4C0180E48C9C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"92c1f0b8a1bdd62e65a850d8a33633f79f6a8326","datavalue":{"value":{"text":"A linear algorithm for finding \\([g,f]\\)-colorings of partial \\(k\\)-trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1578404$193EACF2-F02E-408B-B07D-6A1276A863A9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a9b72e2b293d7589689ce74d3e1e5d6dbfafb2f9","datavalue":{"value":"0971.05048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578404$997D3968-B29B-4350-8C02-B1FB49D909EE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e9dd54233527279392162fc8991b89f7478f2f19","datavalue":{"value":{"entity-type":"item","numeric-id":1578403,"id":"Q1578403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578404$211C4A20-6D00-488E-8F08-D689D04B9B76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"afe6b2fafd1f610776abf3a55879f526da328740","datavalue":{"value":{"entity-type":"item","numeric-id":226823,"id":"Q226823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578404$76732977-2C3B-4040-A4AB-41BD93030E91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"da93d7c45d552338138e673e141df03679ac5cb5","datavalue":{"value":{"entity-type":"item","numeric-id":226821,"id":"Q226821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578404$88B21862-5D44-4415-8A99-63388C276EC4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578404$10C480E4-77F0-4A24-9EF7-1EFE7A1D6626","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"807acfe2abaa92e89310133eb1e395950faeb629","datavalue":{"value":{"time":"+2001-10-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":"Q1578404$7D4164DB-09B8-4586-8ADF-BC25E4FC69B8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"74d16b3638933dc1ab9f3975731e9d0ddbaeb971","datavalue":{"value":"A \\([g,f]\\)-coloring is a generalized edge-coloring in which each color appears at each vertex \\(v\\) at least \\(g(v)\\) and at most \\(f(v)\\) times, where \\(g(v)\\) and \\(f(v)\\) are respectively nonnegative and positive integers assigned to \\(v\\). The paper gives a linear-time algorithm to find a \\([g,f]\\)-coloring of a given partial \\(k\\)-tree using the minimum number of colors, if \\(k\\) and \\(f\\) are bounded and such a coloring exists. Recursively defined partial \\(k\\)-trees include trees \\((k=1)\\), outerplanar and series-parallel graphs \\((k=2)\\) and Halin graphs \\((k=3)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578404$441AE436-1945-47FB-B5ED-198994D3E42D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"db03c62d3fdb76a66177e81b54d14a2f5ae490f1","datavalue":{"value":{"entity-type":"item","numeric-id":237429,"id":"Q237429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1578404$315DEBBE-1470-453C-859D-6F2BCDA54DE6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578404$018F2224-2AE2-46F6-8766-98F74C0E4692","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578404$E6F6E272-576E-4F02-B601-F18CF1927BCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578404$1C14C4FC-34DD-44B5-AB1B-F7A242279FA6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ddba916eb8b0b42cb51c985b3d2a3ce81d19ad3c","datavalue":{"value":"1496843","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578404$1AA2EC7F-5FED-4312-AE2A-A7831831D801","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a711949b401a7bc26ae2ce806f52f7c535a9bb2","datavalue":{"value":"bounded treewidth","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578404$339A6F8C-ED2D-491A-9776-B3733D266548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5460c444abb9d7604f90c4e16cd9cc2ad2a35457","datavalue":{"value":"edge-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578404$0F3AF384-B5F2-4A89-9BC1-37F4790C715B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5186fd99999e6921db65766363ee98e6a615dadc","datavalue":{"value":"linear-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578404$5A321870-D4F8-4B5F-A8C1-81D109D2DBC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"211a09b137bdf42f268c86e50a34a0d25fd19aa0","datavalue":{"value":"partial \\(k\\)-tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578404$D71E13BA-902C-40A2-873D-273C7AC979A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bce15aac2ad6b3166943c4d968d9cbcfb14a31cb","datavalue":{"value":"Halin graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1578404$5E2C686B-1EE2-4A43-88A5-1167F57A5816","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":"Q1578404$B31A7B1C-A03F-4BC4-9D86-9C216A922390","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a9adafabff1960e9d5807b2730d07a4a2eb6b773","datavalue":{"value":"https://doi.org/10.1007/s004530010017","type":"string"},"datatype":"url"},"type":"statement","id":"Q1578404$5F604CA6-2C67-44AC-912A-85978F722D49","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6e7d5281f45cdb612ec73928b383200ea74ae2b8","datavalue":{"value":"W2019023526","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578404$65D96A32-EEAF-4D2D-B2E2-19F2580DD8A3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"294a401f712ec5510a02d10850d9424a5cc1c35b","datavalue":{"value":"10.1007/S004530010017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1578404$31D72AB1-C010-41A6-A092-9F5525C07C6A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52b34e1199b85ab9abcff0de6c610b8e0c164a0f","datavalue":{"value":{"entity-type":"item","numeric-id":6487980,"id":"Q6487980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c57f94d3626a50b88b6183aeac7eb540dc44a3cf","datavalue":{"value":{"amount":"+0.924033522605896","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":"Q1578404$5FE2F8B7-5A9C-4721-BFCF-D892770377F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"314a452a7a12380b9b84e2650d4d314dd4311d4d","datavalue":{"value":{"entity-type":"item","numeric-id":3837389,"id":"Q3837389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73bc02c28fe74a8ee39669d451aab472f2ae597e","datavalue":{"value":{"amount":"+0.8779042959213257","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":"Q1578404$53F9AD82-568D-4B25-A36F-5B1A8A6CAFE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a1c2b16350c893a99eb0f524183cd4faece094d","datavalue":{"value":{"entity-type":"item","numeric-id":4511238,"id":"Q4511238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bcf68abf3df66794c08abab4cf742782ebff00df","datavalue":{"value":{"amount":"+0.8625848889350891","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":"Q1578404$A77AA071-8F40-4D91-96CB-155B392A5AFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f141654b64bcc73fbcec895d0e55612bf9ae4738","datavalue":{"value":{"entity-type":"item","numeric-id":5248998,"id":"Q5248998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44e54684c79a40e890b0383abc420d06d52c8467","datavalue":{"value":{"amount":"+0.8563702702522278","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":"Q1578404$3FB718E4-EA69-4D9F-9983-7031233DD18E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1578404","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1578404"}}}}}