{"entities":{"Q1363684":{"pageid":1374423,"ns":120,"title":"Item:Q1363684","lastrevid":43059869,"modified":"2025-07-17T08:19:04Z","type":"item","id":"Q1363684","labels":{"en":{"language":"en","value":"LexBFS-orderings and powers of chordal graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1047077"}},"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":"Q1363684$143DDAE1-E803-4123-A2B2-058319BC6935","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"84273beb3aa0c757435e3599970c24a2de57c1c4","datavalue":{"value":{"text":"LexBFS-orderings and powers of chordal graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1363684$CABEF334-43DB-4E5E-8BC8-86FB0A79F233","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c26923dc572dc9bd55c9fd66d3381f8667f07807","datavalue":{"value":"0880.05074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363684$8C36D5F3-AD2D-459C-B17A-F333A311A389","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9fded0c1aa440bd97f0b9f0f31b46041995dff40","datavalue":{"value":"10.1016/S0012-365X(96)00070-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363684$5491F8C7-62F0-47E2-9098-737E2EC08D1F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbb68d9de22321af7fb543db220c0a16a741857c","datavalue":{"value":{"entity-type":"item","numeric-id":170457,"id":"Q170457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363684$DBFF8715-7467-4884-9598-4F88A8DD93BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"97dbd21a3cbf1118b1d651db6d325ca352db3dc3","datavalue":{"value":{"entity-type":"item","numeric-id":221665,"id":"Q221665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363684$D47D9566-F77C-4E2E-8F47-72E276B2C6E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5e8ce6f4aa1d9a57c198704c5bacc005467d56f6","datavalue":{"value":{"entity-type":"item","numeric-id":685526,"id":"Q685526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363684$9390CBEA-E016-4A72-B568-9436C5B6B7E5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363684$70707056-B725-4FEA-BFD0-6B7A67F677FB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e923552579303fe8b30d2a139bb2fde0734b1912","datavalue":{"value":{"time":"+1998-01-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1363684$B67FF5C7-C478-4A25-8D42-DC136D18F8D6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"02ac91397671e63ef970e90b496f258fe2a881f9","datavalue":{"value":"Two vertices of the \\(k\\)th power of a graph \\(G\\) are adjacent if and only if their distance in \\(G\\) does not exceed \\(k\\). The lexicographic breadth-first-search (LexBFS) [see \\textit{D. J. Rose}, \\textit{R. E. Tarjan} and \\textit{G. S. Lueker}, SIAM J. Comput. 5, 266-283 (1976; Zbl 0353.65019)] and the maximum cardinality search (MCS) [see \\textit{R. E. Tarjan} and \\textit{M. Yannakakis}, SIAM J. Comput. 13, 566-579 (1984; Zbl 0545.68062)] give a perfect elimination ordering of a chordal graph in linear time [see \\textit{M. C. Golombic}, Algorithmic graph theory and perfect graphs (1980; Zbl 0541.05054)]. In this paper the authors prove that the LexBFS-ordering of a chordal graph is a common perfect elimination ordering of all odd powers of this graph. Also results concerning even powers and MCS are presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1363684$0B33274D-CE15-4557-A9AC-D4EF40A96193","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"28b1fb367b3a6335e647ddbd540f63d134723dd1","datavalue":{"value":{"entity-type":"item","numeric-id":222481,"id":"Q222481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363684$E4A88A56-53F5-4C88-A5DA-26D1F4AC96DB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363684$46EFD911-5DD5-4CC7-BE45-C974D0344546","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363684$D0938280-7038-4398-A388-0703B9B509C8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4e94b85dc1308e325c318d21c2cb167352fdcd99","datavalue":{"value":"1047077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363684$4C351D79-193F-4710-A531-0C95019CE55C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"00b378859afdb68c30844c3d745b6b412b44cbdd","datavalue":{"value":"elimination ordering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1363684$C0BC7CC8-DEAE-4FDA-A1D2-DEE3F240B310","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae41303426e6695786e3a6d28699919bfeab34a","datavalue":{"value":"chordal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1363684$77B69C3C-AE49-44AC-9B6E-176ED9751DF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"932a7ef40d809d712df9640feabd1ae110ccb245","datavalue":{"value":"powers","type":"string"},"datatype":"string"},"type":"statement","id":"Q1363684$9753406A-679B-452C-9AC3-3DC4D720F1E1","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":"Q1363684$7558BDC0-2145-4671-A802-C155DED8DEB4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"32c1a4180aeef07849b9be70ab86fcca0a7db8ca","datavalue":{"value":{"entity-type":"item","numeric-id":1815326,"id":"Q1815326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363684$42D4828D-272E-4961-9A64-536E0D04F7E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65552a1f5a18af5e53ec309347e69493fd8f33b1","datavalue":{"value":{"entity-type":"item","numeric-id":4942657,"id":"Q4942657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363684$EBE9897A-915B-48E2-A358-48C747471233","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebd0293f4bb61e0400a6439bf5b2433073065c05","datavalue":{"value":{"entity-type":"item","numeric-id":3222876,"id":"Q3222876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363684$70C77537-25E8-4B65-9A85-6CDC611137CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1fc23e3fdbc14d592d2bb540feda88d75a3ba44","datavalue":{"value":{"entity-type":"item","numeric-id":3718757,"id":"Q3718757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363684$7A01A475-90A2-4822-B1CB-82723C630AB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363684$354C95B2-242D-4BE4-9697-C0B6B87A933A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79981124712be007c2eddc8be25e8e3e4dfef1f5","datavalue":{"value":{"entity-type":"item","numeric-id":1825204,"id":"Q1825204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363684$0059E3EE-D7B6-414B-BCB9-CAD358B5083E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"937795a144c8ec9cb492dda6b948f0e6d73db8b3","datavalue":{"value":{"entity-type":"item","numeric-id":1055453,"id":"Q1055453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363684$577BD65B-3ADD-410F-9143-0B4959F1A52D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8592b19f12bd09556a4de81ad49778d747c4f77b","datavalue":{"value":{"entity-type":"item","numeric-id":4124209,"id":"Q4124209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363684$38A82158-9C46-477C-97D9-837867A2384B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bba15cf4a9d2c986ffe8184ac3a6d051fff29cb","datavalue":{"value":{"entity-type":"item","numeric-id":3335007,"id":"Q3335007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363684$FF886F16-CAF5-4DE3-9BF8-45AFB348B894","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49852327a29a30b2f7656fe5f7be1fb0d186a452","datavalue":{"value":{"entity-type":"item","numeric-id":4254590,"id":"Q4254590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a800811d941a1e5a4502fb69837d2f1a6b32993","datavalue":{"value":{"amount":"+0.9315574","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":"Q1363684$01DB51D1-C476-4B4E-BC78-3A4402D77FDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"adf1a0f4be77f6167f1c10726ed882a0406812f7","datavalue":{"value":{"entity-type":"item","numeric-id":1815326,"id":"Q1815326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a54bb48438d07d43ed04233ca970d5e331a4e38c","datavalue":{"value":{"amount":"+0.88561153","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":"Q1363684$E83128AC-0B62-4F0A-BDD4-D6DA78EBDAF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f7878407059a4fe9acbfc3dcc98b67420abd31f","datavalue":{"value":{"entity-type":"item","numeric-id":1962066,"id":"Q1962066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9590562d8664c4fa614f001030faa964cbdaf14","datavalue":{"value":{"amount":"+0.8802582","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":"Q1363684$11039AD9-872E-4309-B016-189A244CA8D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d50777ea9e897c22c44841d00572bec9d26c701","datavalue":{"value":{"entity-type":"item","numeric-id":3647340,"id":"Q3647340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f64c62cb3c35d37a1113d6ce8ff8de02d8d9c4e5","datavalue":{"value":{"amount":"+0.87415826","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":"Q1363684$DE010CE8-BB22-42F3-A27D-D46FD438AE8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6a554707ff6b09c15c8553760b3ce0b813143f0","datavalue":{"value":{"entity-type":"item","numeric-id":673001,"id":"Q673001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bae224d5cfb021ec27bd126bf42235cd8f3f6e1d","datavalue":{"value":{"amount":"+0.87261915","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":"Q1363684$B4EC125D-42E6-4B3C-BE14-355E54A7D994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"993284880f7a3e2b32ad78d1cbc3af5455d02865","datavalue":{"value":{"entity-type":"item","numeric-id":4511223,"id":"Q4511223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e6e01d16e01d97a254d93ecb46be495fe13771a","datavalue":{"value":{"amount":"+0.87249446","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":"Q1363684$7EF888A0-AFAA-4B32-BF15-22D5AD4DD8F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6143b62a01f4d60c0486a3aa370ac181af5e9cc5","datavalue":{"value":{"entity-type":"item","numeric-id":5874479,"id":"Q5874479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9be93022c1e1d53fdbf393bd353130e3c6b23e2e","datavalue":{"value":{"amount":"+0.8717603","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":"Q1363684$19F395CE-D558-4A6A-8F0D-E9B98D3DE664","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b218f0435ac5fe500e013720747ea5ffaf825095","datavalue":{"value":{"entity-type":"item","numeric-id":1182042,"id":"Q1182042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"664506890ce532c4fdf519113d2584d0dbbbdc28","datavalue":{"value":{"amount":"+0.86983204","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":"Q1363684$18825C7B-AFE4-44CE-AD0E-2C419CE434F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e8da9dc5cb3a4d4b62934d6e6c167ef22bc8222","datavalue":{"value":{"entity-type":"item","numeric-id":4252390,"id":"Q4252390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2f37c3f9ff56e156ea0645c61d89e3495a2c3cd","datavalue":{"value":{"amount":"+0.86886334","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":"Q1363684$E60AD1DC-8CB8-4462-A688-56CF55AE198B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d79f961d06567838aefedf6558c25e7c17a378ae","datavalue":{"value":{"entity-type":"item","numeric-id":3481747,"id":"Q3481747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9661a04ad5721f80aa393cd27ab906770fc7ffa","datavalue":{"value":{"amount":"+0.8656844","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":"Q1363684$D614A0AE-3FB1-4AB2-90F3-9585DE454A3A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1363684","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1363684"}}}}}