{"entities":{"Q612969":{"pageid":614745,"ns":120,"title":"Item:Q612969","lastrevid":63050586,"modified":"2026-04-11T10:05:47Z","type":"item","id":"Q612969","labels":{"en":{"language":"en","value":"Linear programming and the worst-case analysis of greedy algorithms on cubic graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5827426"}},"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":"Q612969$F0A7C5DF-7246-4D8E-AF82-9C92A3606286","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3ad8c7968dd3eaced00f01ca8c0306d1516a7329","datavalue":{"value":{"text":"Linear programming and the worst-case analysis of greedy algorithms on cubic graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q612969$1A1892FF-EAF5-4DD9-9FC3-F1C08C5B0F53","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b3cac1bdd976e19ffa97a765b3e57b67c430ecad","datavalue":{"value":"1204.05090","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612969$811C3478-F729-4AFA-8CAF-1C534C3DE90C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q612969$7853DEA9-C71A-47AA-B7AA-7DB816F00376","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63d0db48794e6800d8c22359b1f6c876c0e4d309","datavalue":{"value":{"time":"+2010-12-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q612969$A6065E53-FC26-4C80-843E-FA39F1C0163C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f64d7326e1b870d32058bc51eb4496742ee50b36","datavalue":{"value":"https://eudml.org/doc/226613","type":"string"},"datatype":"url"},"type":"statement","id":"Q612969$CA89BC21-DC9D-4EE3-9E5F-6A919A45237F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"cae0ad4a891e7c9936f662aefffcb2130f7b0cb1","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r177.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q612969$D770A08A-74A8-4795-B43A-76FD23425032","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f8236d24d40855d22d964c73aca9020d7c6355a7","datavalue":{"value":"We introduce a technique using linear programming that may be used to analyse the worst-case performance of a class of greedy heuristics for certain optimisation problems on regular graphs. We demonstrate the use of this technique on heuristics for bounding the size of a minimum maximal matching (MMM), a minimum connected dominating set (MCDS) and a minimum independent dominating set (MIDS) in cubic graphs. We show that for \\(n\\)-vertex connected cubic graphs, the size of an MMM is at most \\(9n/20+O(1)\\), which is a new result. We also show that the size of an MCDS is at most \\(3n/4+ O(1)\\) and the size of a MIDS is at most \\(29n/70+ O(1)\\). These results are not new, but earlier proofs involved rather long ad-hoc arguments. By contrast, our method is to a large extent automatic and can apply to other problems as well. We also consider n-vertex connected cubic graphs of girth at least 5 and for such graphs we show that the size of an MMM is at most \\(3n/7+O(1)\\), the size of an MCDS is at most \\(2n/3+O(1)\\) and the size of a MIDS is at most \\(3n/8+O(1)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q612969$1F7C5498-06B5-46E3-B64F-4A347B638ED1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612969$30C1E27A-457A-4665-9D5C-9EBC9A489D54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612969$ADFF3A4E-B995-40C8-92EF-A5FED81054FB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0169d01ed49290d6cab31eca122b5f356747c493","datavalue":{"value":"5827426","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612969$378D1DE9-3E06-4D2A-B6BA-9A986EE57E3C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"14f5692e185b1488dd97e357834d4b024a1d4fa4","datavalue":{"value":"worst-case analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q612969$4C40DFB1-F814-4A31-948E-175C320A0685","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa6068f74429336d5aa4dfd9ab7fed8cf06f35c1","datavalue":{"value":"cubic","type":"string"},"datatype":"string"},"type":"statement","id":"Q612969$1B6D38DF-0427-44CB-8F64-DD8206730B1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a53d3835808f97ffefac51074ee0172bbf736a55","datavalue":{"value":"3-regular","type":"string"},"datatype":"string"},"type":"statement","id":"Q612969$A694C87F-6794-4EC9-A5BD-367743A1FAA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3e2c5cdbb9bf737c4fa7ac78971f831677d8a1d","datavalue":{"value":"graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q612969$AFF25854-AE33-49A0-9359-11C2716DA550","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a08efa1a08a750d06fca0196004a17a02a35c592","datavalue":{"value":"linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q612969$7A49DE4F-5946-46EB-98A3-56F1CE87C63D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cd1fe0a9e76938122d0c147e022b872272d0a9bb","datavalue":{"value":{"entity-type":"item","numeric-id":876694,"id":"Q876694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q612969$35FC530B-6CC6-4C80-9523-B61C61FA5AFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c84290e2aa59f5e72197dc6c42e23718498784e5","datavalue":{"value":{"entity-type":"item","numeric-id":704840,"id":"Q704840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q612969$3AE32007-E875-43C6-9788-46CBDEF88A8A","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":"Q612969$736714E0-861F-499B-B5B8-21C3E78DD515","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"2c01f09a5f93b9fd831f9ed5012cff0f517832c5","datavalue":{"value":"bafkreicamjbgq4qoa6hqopmvjkct2hiq37rbuxlprvzgojtpx4x5arjyo4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612969$9FCAE655-05BC-4321-89BA-9AA74C186C20","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"829eebe49ee8833a3be316c1c24993e96954e43f","datavalue":{"value":{"entity-type":"item","numeric-id":1373761,"id":"Q1373761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53deaaaf29c859be802dff7e54d6839fabe46e97","datavalue":{"value":{"amount":"+0.87996686","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":"Q612969$DAE899D2-7AE3-4F58-9C87-8ECE5D30F4CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5c1952f1b7620aa43a4ab83bd4a6196d7e34933","datavalue":{"value":{"entity-type":"item","numeric-id":3768677,"id":"Q3768677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65bd1cbbbd097930eebb7fc5936ee75250d82fa0","datavalue":{"value":{"amount":"+0.8789856","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":"Q612969$CC0F9CA2-5953-465F-82E4-C76D0C07C65B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f03d4f5f54cdf44e8349f5628d7e8c249e72dd3","datavalue":{"value":{"entity-type":"item","numeric-id":1290661,"id":"Q1290661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d12d1894cd54a3629fc969532479b4089212b27b","datavalue":{"value":{"amount":"+0.8755089","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":"Q612969$9555C0B6-B342-471E-9C48-8CF6249EFAFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e9f0439ee4bd791b71cbe759ed507f412190a34","datavalue":{"value":{"entity-type":"item","numeric-id":5463458,"id":"Q5463458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78584a36d0cc37ea1f1ef07a7311ceb8cbf2842d","datavalue":{"value":{"amount":"+0.8722228","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":"Q612969$369C967B-5860-4DFA-9F7E-DB97C827370D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e07f4c50da02a3d142f478c1f4282e81d986068","datavalue":{"value":{"entity-type":"item","numeric-id":4731220,"id":"Q4731220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b81ea5557037e805c5e13dc1f95d464530b5e28a","datavalue":{"value":{"amount":"+0.8710166","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":"Q612969$0FF4047B-9EE3-435B-A9A8-B5C6C65FF5A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"61da8ac78231aeb8b55bdaa5dfc235596aaf777e","datavalue":{"value":{"entity-type":"item","numeric-id":1007554,"id":"Q1007554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4eec642e0682d256ef06f276a2d85258234ebd0","datavalue":{"value":{"amount":"+0.8696343","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":"Q612969$B9E24128-A224-41A1-98AB-8C9EA67D92A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db4258d8fad941ec9746322adaa120158e7b41e9","datavalue":{"value":{"entity-type":"item","numeric-id":2868311,"id":"Q2868311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db268a4555aff52afdf0934c1aa95811e01df473","datavalue":{"value":{"amount":"+0.86738944","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":"Q612969$4D17120E-71F0-4F50-B7CD-50E30ED288EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"456d4bc0da531ac11191ea85657355b7639bad7a","datavalue":{"value":{"entity-type":"item","numeric-id":4234156,"id":"Q4234156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a394b73cf7345005ebf9885d0e1da2b7b2ac6ca0","datavalue":{"value":{"amount":"+0.8658107","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":"Q612969$C37EE551-024A-4A0A-8FD1-829FD1BAABE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1de6be1995d126d76179f40a3357c482174d7782","datavalue":{"value":{"entity-type":"item","numeric-id":2757571,"id":"Q2757571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a394b73cf7345005ebf9885d0e1da2b7b2ac6ca0","datavalue":{"value":{"amount":"+0.8658107","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":"Q612969$B0ED5275-3CED-43D4-9240-6105A2F995E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4cf4557adfaa4afb328c49207c7246a704942f56","datavalue":{"value":{"entity-type":"item","numeric-id":4844489,"id":"Q4844489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f081de73671278aeadd51253aa0110135a667bc","datavalue":{"value":{"amount":"+0.865521","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":"Q612969$E236DE5D-7ECF-4BAA-8E1F-E765E8935C0C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Linear programming and the worst-case analysis of greedy algorithms on cubic graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Linear_programming_and_the_worst-case_analysis_of_greedy_algorithms_on_cubic_graphs"}}}}}