{"entities":{"Q674917":{"pageid":676766,"ns":120,"title":"Item:Q674917","lastrevid":46764006,"modified":"2025-12-25T13:26:18Z","type":"item","id":"Q674917","labels":{"en":{"language":"en","value":"A linear-time algorithm for computing the intersection of all odd cycles in a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 987766"}},"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":"Q674917$441AB777-D395-4848-ADD0-AADDAE677CB9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b040e97da1af3527963e51fbe6f20d8501b125b4","datavalue":{"value":{"text":"A linear-time algorithm for computing the intersection of all odd cycles in a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q674917$0A3E70A9-0423-4FED-B840-F26CD04516FA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f1c562dc531342bbfcaa5401a3e642e430254a98","datavalue":{"value":"0867.05066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674917$10920102-90F2-403C-9D58-110A609E5EB7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4f9253a75d33b99a8cd9bbd1462bd2280021d166","datavalue":{"value":"10.1016/S0166-218X(96)00074-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674917$3E9A7D3A-0E41-41A5-831A-9AA557FB21B9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f00237d5739b07662cb51e9e957100249e47b2d2","datavalue":{"value":{"entity-type":"item","numeric-id":175508,"id":"Q175508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674917$C1906768-4172-4069-9890-A453CBB7E21D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dff9feb3c5b84d40611faa1bb1e3fe810be17c3e","datavalue":{"value":{"entity-type":"item","numeric-id":221691,"id":"Q221691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674917$1B02C952-0956-4F35-9C79-7389150492B5","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":"Q674917$A2C05470-C5DC-42C5-974E-B666980172B7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b34f93578f34bf813eb265da2a0d58fb3d8dd5ea","datavalue":{"value":{"time":"+1997-08-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q674917$8306C2EA-0325-4C9A-B2DA-E0752F608D0D","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":"Q674917$EA51FC3D-1637-4C63-AC10-6771D4792C94","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f89ddf970df8e0d26e0feca6b9bebc604e62765b","datavalue":{"value":"The authors consider the problem of finding edges and vertices in a graph \\(G\\) that are contained in every odd cycle of \\(G\\). This problem is partially motivated by a fixed-parameter version of two well-known NP-complete problems. A characterization of the intersection of all odd cycles in a graph \\(G\\) is proposed by using the intersection of the \\(T\\)-spans of all monochromatic edges (\\(T\\) is a spanning tree of \\(G\\)) and the partial subgraph of \\(G\\) obtained by removing all monochromatic edges. Using this result, a linear-time algorithm is then exhibited. An application of this algorithm is given to a satisfiability problem, namely the minimum mono-valued 2SAT.","type":"string"},"datatype":"string"},"type":"statement","id":"Q674917$DFE40465-718D-4BD6-874C-014DED731D81","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674917$DDABFC49-FAC7-4603-9502-47412179B120","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674917$12CCC859-A65C-4992-85E3-EB049A992090","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674917$D50231FC-2571-416A-9019-B74AE54F2DB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674917$626DD822-3250-42DC-9801-8A0C28E90544","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"97c543f8c5b4534822721d0b822da42a3caa5535","datavalue":{"value":"987766","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q674917$D31FD91E-0ECB-4DB6-83C3-C5EC7B1A74D8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6632d6c62ffd85f90b0b4aa23149cd1a8c7ae150","datavalue":{"value":"odd cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q674917$3CA7FD39-FBDC-4514-85D0-5A858EE9080B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5186fd99999e6921db65766363ee98e6a615dadc","datavalue":{"value":"linear-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q674917$DC89CFEE-0279-4F33-ACB2-0474CB18E46B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"252f9f9ed9fe8ca406cc19fba38a46c0414791ee","datavalue":{"value":"satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q674917$87940DD9-7760-413D-8D31-089DAEAF05BD","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":"Q674917$C9A964A4-2890-4A60-86A0-A5F6C2FCFE47","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674917$6A9D08B3-D540-4BBB-929A-6B1E8B864866","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d9e735882f0114d9d1bd74d7bde93766d995370","datavalue":{"value":{"entity-type":"item","numeric-id":4065051,"id":"Q4065051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674917$35EE33F2-A6C7-4083-9245-EDE5048053CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674917$23B518AA-CBEF-4122-B3B3-795A60EC4337","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c694e31997a7a457bac1c2971d60584b887f7d1","datavalue":{"value":{"entity-type":"item","numeric-id":1352005,"id":"Q1352005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674917$DAA72092-3C17-4AC1-A5E6-1D035DD5CF5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fa1290987e9e9910315413923140808cd3d7e8a","datavalue":{"value":{"entity-type":"item","numeric-id":4852629,"id":"Q4852629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674917$CA432264-DDEE-473B-9315-81022CE6A431","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674917$AFACD046-869B-4DBD-A2D5-98B3C239251D","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":"Q674917$3721384D-4902-407D-9BAC-ABB6369F80DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674917$9FAC65C9-6B07-48C0-8B1D-A7A4767581B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e759b8ddc389f8b42bb244f19be1adfe6bb34c7","datavalue":{"value":{"entity-type":"item","numeric-id":5402560,"id":"Q5402560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q674917$A78EF14C-1137-4F9E-BF24-D5A403D3083F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97e7e6b4a0dc3f53ea01772c5e92e7305381d422","datavalue":{"value":{"entity-type":"item","numeric-id":703225,"id":"Q703225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff0fe43d9d793da29b063d9fe02812d4b1593d86","datavalue":{"value":{"amount":"+0.7729854583740234","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":"Q674917$ABDEFA34-99DB-4BB9-B84E-FE123A0C4959","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de495a446e65444d7fca66f37ad8b2e8510d2168","datavalue":{"value":{"entity-type":"item","numeric-id":5417631,"id":"Q5417631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bae43bdf4469ea5bf9cec966a00ead8c43df3d60","datavalue":{"value":{"amount":"+0.7484012842178345","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":"Q674917$A1B57E1B-8CB1-4856-9559-E859DA861690","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb3049917426938033361b8d7b8b22217e356d0a","datavalue":{"value":{"entity-type":"item","numeric-id":1272187,"id":"Q1272187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98dc0f7d952df35acf5b4c59387d6a6ce6f67139","datavalue":{"value":{"amount":"+0.7257680296897888","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":"Q674917$E94C24B0-721A-45C8-AA13-6B216E671D5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd6bd9890864aa63e22111efaaf4c4dff33601dd","datavalue":{"value":{"entity-type":"item","numeric-id":813970,"id":"Q813970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3782009a992cf4a717fdd59474d1c3b279724073","datavalue":{"value":{"amount":"+0.7224336266517639","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":"Q674917$09591D75-1460-49D4-A22E-37D6F34FF371","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a489c3fea9b922c65ac59389c60d3b9a745b2f9","datavalue":{"value":{"entity-type":"item","numeric-id":2482113,"id":"Q2482113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b6b08565b400e4f4b1d0a03cc9e5729a76097c1","datavalue":{"value":{"amount":"+0.7196282148361206","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":"Q674917$796FF459-88F5-4FE8-A577-6523E536785B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:674917","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:674917"}}}}}