{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,3]],"date-time":"2024-07-03T23:58:04Z","timestamp":1720051084929},"reference-count":58,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2021,1,10]],"date-time":"2021-01-10T00:00:00Z","timestamp":1610236800000},"content-version":"vor","delay-in-days":1470,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"funder":[{"DOI":"10.13039\/100007595","name":"Belarusian BRFFR","doi-asserted-by":"publisher","award":["F13K-078","F13MLD-012"],"id":[{"id":"10.13039\/100007595","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004794","name":"French CNRS","doi-asserted-by":"publisher","award":["5379"],"id":[{"id":"10.13039\/501100004794","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001655","name":"DAAD","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001655","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2017,1]]},"DOI":"10.1016\/j.dam.2016.08.015","type":"journal-article","created":{"date-parts":[[2016,9,23]],"date-time":"2016-09-23T22:58:29Z","timestamp":1474671509000},"page":"15-28","update-policy":"http:\/\/dx.doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":2,"special_numbering":"P1","title":["Graphs with maximal induced matchings of the same size"],"prefix":"10.1016","volume":"216","author":[{"given":"Philippe","family":"Baptiste","sequence":"first","affiliation":[]},{"given":"Mikhail Y.","family":"Kovalyov","sequence":"additional","affiliation":[]},{"given":"Yury L.","family":"Orlovich","sequence":"additional","affiliation":[]},{"given":"Frank","family":"Werner","sequence":"additional","affiliation":[]},{"given":"Igor E.","family":"Zverovich","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.dam.2016.08.015_br000005","series-title":"Combinatorial-Algebraic Methods in Discrete Optimization","first-page":"5","article-title":"On the number of maximal stable sets in graphs from hereditary classes","author":"Alekseev","year":"1991"},{"key":"10.1016\/j.dam.2016.08.015_br000010","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1109\/JSAC.2004.830909","article-title":"The distance-2 matching problem and its relationship to the MAC-layer capacity of ad hoc wireless networks","volume":"22","author":"Balakrishnan","year":"2004","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"10.1016\/j.dam.2016.08.015_br000015","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1002\/net.3230190206","article-title":"On graphs with polynomially solvable maximum-weight clique problem","volume":"19","author":"Balas","year":"1989","journal-title":"Networks"},{"key":"10.1016\/j.dam.2016.08.015_br000020","series-title":"Beitr\u00e4dge zur Graphentheorie","first-page":"17","article-title":"Derived graphs and digraphs","author":"Beineke","year":"1968"},{"key":"10.1016\/j.dam.2016.08.015_br000025","series-title":"Graphs and Hypergraphs","author":"Berge","year":"1976"},{"key":"10.1016\/j.dam.2016.08.015_br000030","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0020-0190(84)90126-1","article-title":"Dominating sets for split and bipartite graphs","volume":"19","author":"Bertossi","year":"1984","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/j.dam.2016.08.015_br000035","series-title":"Graph Theory with Applications","author":"Bondy","year":"1976"},{"key":"10.1016\/j.dam.2016.08.015_br000040","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/j.tcs.2007.04.006","article-title":"The induced matching and chain subgraph cover problems for convex bipartite graphs","volume":"381","author":"Brandst\u00e4dt","year":"2007","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.dam.2016.08.015_br000045","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1007\/s00453-007-9045-2","article-title":"Maximum induced matchings for chordal graphs in linear time","volume":"52","author":"Brandst\u00e4dt","year":"2008","journal-title":"Algorithmica"},{"key":"10.1016\/j.dam.2016.08.015_br000050","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1016\/j.dam.2010.05.022","article-title":"On distance-3 matchings and induced matchings","volume":"159","author":"Brandst\u00e4dt","year":"2011","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.dam.2016.08.015_br000055","doi-asserted-by":"crossref","first-page":"998","DOI":"10.1007\/s00453-012-9709-4","article-title":"Dominating induced matchings for P7-free graphs in linear time","volume":"68","author":"Brandst\u00e4dt","year":"2014","journal-title":"Algorithmica"},{"key":"10.1016\/j.dam.2016.08.015_br000060","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0166-218X(92)90275-F","article-title":"Induced matchings","volume":"24","author":"Cameron","year":"1989","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.dam.2016.08.015_br000065","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.disc.2003.05.001","article-title":"Induced matchings in intersection graphs","volume":"278","author":"Cameron","year":"2004","journal-title":"Discrete Math."},{"key":"10.1016\/j.dam.2016.08.015_br000070","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/S0012-365X(02)00803-8","article-title":"Finding a maximum induced matching in weakly chordal graphs","volume":"266","author":"Cameron","year":"2003","journal-title":"Discrete Math."},{"key":"10.1016\/j.dam.2016.08.015_br000075","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.disc.2004.07.022","article-title":"The graphs with maximum induced matching and maximum matching the same size","volume":"299","author":"Cameron","year":"2005","journal-title":"Discrete Math."},{"key":"10.1016\/j.dam.2016.08.015_br000080","first-page":"193","article-title":"A characterization of well-covered cubic graphs","volume":"13","author":"Campbell","year":"1993","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"10.1016\/j.dam.2016.08.015_br000085","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1137\/S0895480196300479","article-title":"Local structure when all maximal independent sets have equal weight","volume":"11","author":"Caro","year":"1998","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/j.dam.2016.08.015_br000090","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1006\/jagm.1996.0006","article-title":"Recognizing greedy structures","volume":"20","author":"Caro","year":"1996","journal-title":"J. Algorithms"},{"key":"10.1016\/j.dam.2016.08.015_br000095","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/S0166-218X(03)00390-1","article-title":"Induced matchings in asteroidal triple-free graphs","volume":"132","author":"Chang","year":"2003","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.dam.2016.08.015_br000100","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/S0167-5060(08)70387-X","article-title":"A note on well-covered graphs","volume":"55","author":"Chv\u00e1tal","year":"1993","journal-title":"Ann. Discrete Math."},{"key":"10.1016\/j.dam.2016.08.015_br000105","series-title":"Proc. 3rd Ann. ACM Symp. on Theory of Computing","first-page":"151","article-title":"The complexity of theorem proving procedure","author":"Cook","year":"1971"},{"key":"10.1016\/j.dam.2016.08.015_br000110","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/j.tcs.2013.01.027","article-title":"New results on maximum induced matchings in bipartite graphs and beyond","volume":"478","author":"Dabrowski","year":"2013","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.dam.2016.08.015_br000115","first-page":"5","article-title":"Well-dominated graphs: a collection of well-covered ones","volume":"25A","author":"Finbow","year":"1988","journal-title":"Ars. Gomb."},{"key":"10.1016\/j.dam.2016.08.015_br000120","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1006\/jctb.1993.1005","article-title":"A characterization of well-covered graphs of girth 5 or greater","volume":"57","author":"Finbow","year":"1993","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/j.dam.2016.08.015_br000125","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/S0166-218X(03)00393-7","article-title":"On well-covered triangulations: Part I","volume":"132","author":"Finbow","year":"2004","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.dam.2016.08.015_br000130","doi-asserted-by":"crossref","first-page":"2799","DOI":"10.1016\/j.dam.2009.03.014","article-title":"On well-covered triangulations: Part II","volume":"157","author":"Finnow","year":"2009","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.dam.2016.08.015_br000135","doi-asserted-by":"crossref","first-page":"894","DOI":"10.1016\/j.dam.2009.08.002","article-title":"On well-covered triangulations: Part III","volume":"158","author":"Finbow","year":"2010","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.dam.2016.08.015_br000140","doi-asserted-by":"crossref","first-page":"666","DOI":"10.4153\/CJM-1977-069-1","article-title":"Split graphs having Dilworth number two","volume":"29","author":"F\u00f6ldes","year":"1977","journal-title":"Canad. J. Math."},{"key":"10.1016\/j.dam.2016.08.015_br000145","series-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/j.dam.2016.08.015_br000150","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/S0166-218X(99)00194-8","article-title":"New results on induced matchings","volume":"101","author":"Golumbic","year":"2000","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.dam.2016.08.015_br000155","doi-asserted-by":"crossref","first-page":"701","DOI":"10.4153\/CMB-1965-051-3","article-title":"On Eulerian and Hamiltonian graphs and line graphs","volume":"8","author":"Harary","year":"1965","journal-title":"Canad. Math. Bull."},{"key":"10.1016\/j.dam.2016.08.015_br000160","first-page":"35","article-title":"Equipackable graphs","volume":"46","author":"Hartnell","year":"2006","journal-title":"Bull. Inst. Combin. Appl."},{"key":"10.1016\/j.dam.2016.08.015_br000165","series-title":"Fundamentals of Domination in Graphs","author":"Haynes","year":"1998"},{"key":"10.1016\/j.dam.2016.08.015_br000170","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/j.disc.2005.12.003","article-title":"Minimal triangulations of graphs: A survey","volume":"306","author":"Heggernes","year":"2006","journal-title":"Discrete Math."},{"key":"10.1016\/j.dam.2016.08.015_br000175","doi-asserted-by":"crossref","first-page":"1906","DOI":"10.1137\/S0097539796303044","article-title":"Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs","volume":"28","author":"Kaplan","year":"1999","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.dam.2016.08.015_br000180","series-title":"Proc. 10th Ann. ACM Symp. on Theory of Computing","first-page":"240","article-title":"On the complexity of a generalized matching problem","author":"Kirkpatrick","year":"1978"},{"key":"10.1016\/j.dam.2016.08.015_br000185","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1137\/0212040","article-title":"On the complexity of general graph factor problems","volume":"12","author":"Kirkpatrick","year":"1983","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.dam.2016.08.015_br000190","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1137\/S089548019828371X","article-title":"Bipartite domination and simultaneous matroid covers","volume":"16","author":"Ko","year":"2003","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/j.dam.2016.08.015_br000195","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/s00453-003-1035-4","article-title":"Finding maximum induced matchings in subclasses of claw-free and P5-free graphs, and in graphs with matching and induced matching of equal maximum size","volume":"37","author":"Kobler","year":"2003","journal-title":"Algorithmica"},{"key":"10.1016\/j.dam.2016.08.015_br000200","series-title":"Graphs Theory and Combinatorics","first-page":"239","article-title":"Equimatchable graphs","author":"Lesk","year":"1984"},{"key":"10.1016\/j.dam.2016.08.015_br000205","series-title":"Matching Theory","author":"Lov\u00e1sz","year":"1986"},{"key":"10.1016\/j.dam.2016.08.015_br000210","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/j.ipl.2003.07.004","article-title":"Some results on graphs without long induced paths","volume":"88","author":"Lozin","year":"2003","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/j.dam.2016.08.015_br000215","doi-asserted-by":"crossref","first-page":"584","DOI":"10.1016\/j.disopt.2007.11.010","article-title":"Approximability results for the maximum and minimum maximal induced matching problems","volume":"5","author":"Orlovich","year":"2008","journal-title":"Discrete Optim."},{"key":"10.1016\/j.dam.2016.08.015_br000220","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/S0021-9800(70)80011-4","article-title":"Some covering concepts in graphs","volume":"8","author":"Plummer","year":"1970","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/j.dam.2016.08.015_br000225","first-page":"20","article-title":"Well-covered graphs","volume":"2","author":"Ravindra","year":"1977","journal-title":"J. Comb. Inf. Syst. Sci."},{"key":"10.1016\/j.dam.2016.08.015_br000230","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1002\/net.3230220304","article-title":"Complexity results for well-covered graphs","volume":"22","author":"Sankaranarayana","year":"1992","journal-title":"Networks"},{"key":"10.1016\/j.dam.2016.08.015_br000235","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/0020-0190(82)90077-1","article-title":"NP-completeness of some generalizations of the maximum matching problem","volume":"15","author":"Stockmeyer","year":"1982","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/j.dam.2016.08.015_br000240","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1006\/jctb.1996.0022","article-title":"Well-covered claw-free graphs","volume":"66","author":"Tankus","year":"1996","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/j.dam.2016.08.015_br000245","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1006\/jctb.1996.1742","article-title":"The structure of well-covered graphs and the complexity of their recognition problems","volume":"69","author":"Tankus","year":"1997","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/j.dam.2016.08.015_br000250","doi-asserted-by":"crossref","first-page":"1833","DOI":"10.1016\/j.disc.2006.09.031","article-title":"Greedily constructing Hamiltonian paths, Hamiltonian cycles and maximum linear forests","volume":"307","author":"Tankus","year":"2007","journal-title":"Discrete Math."},{"key":"10.1016\/j.dam.2016.08.015_br000255","doi-asserted-by":"crossref","first-page":"2180","DOI":"10.1016\/j.disc.2008.04.047","article-title":"Greedily constructing maximal partial f-factors","volume":"309","author":"Tankus","year":"2009","journal-title":"Discrete Math."},{"key":"10.1016\/j.dam.2016.08.015_br000260","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0166-218X(94)00073-9","article-title":"Well irredundant graphs","volume":"63","author":"Topp","year":"1995","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.dam.2016.08.015_br000265","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/0206036","article-title":"A new algorithm for generating all maximal independent sets","volume":"6","author":"Tsukiyama","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.dam.2016.08.015_br000270","series-title":"Graph Theory","author":"Tutte","year":"1984"},{"key":"10.1016\/j.dam.2016.08.015_br000275","doi-asserted-by":"crossref","first-page":"674","DOI":"10.1016\/j.ejc.2011.01.009","article-title":"A short proof of the Berge\u2013Tutte Formula and the Gallai\u2013Edmonds Structure Theorem","volume":"32","author":"West","year":"2011","journal-title":"European J. Combin."},{"key":"10.1016\/j.dam.2016.08.015_br000280","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1002\/(SICI)1097-0037(199910)34:3<221::AID-NET7>3.0.CO;2-M","article-title":"Modeling k-coteries by well-covered graphs","volume":"34","author":"Yamashita","year":"1999","journal-title":"Networks"},{"key":"10.1016\/j.dam.2016.08.015_br000285","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1137\/0602010","article-title":"Computing the minimum fill-in is NP-complete","volume":"2","author":"Yannakakis","year":"1981","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"10.1016\/j.dam.2016.08.015_br000290","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF02675790","article-title":"A characterization of well-covered graphs in terms of forbidden costable subgraphs","volume":"67","author":"Zverovich","year":"2000","journal-title":"Math. Notes"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X16303924?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X16303924?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,1,13]],"date-time":"2021-01-13T02:16:25Z","timestamp":1610504185000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X16303924"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1]]},"references-count":58,"alternative-id":["S0166218X16303924"],"URL":"https:\/\/doi.org\/10.1016\/j.dam.2016.08.015","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2017,1]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Graphs with maximal induced matchings of the same size","name":"articletitle","label":"Article Title"},{"value":"Discrete Applied Mathematics","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.dam.2016.08.015","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2016 Elsevier B.V.","name":"copyright","label":"Copyright"}]}}