Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ ZENODOarrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
ZENODO
Article . 2016
License: CC BY
Data sources: Datacite
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
ZENODO
Article . 2016
License: CC BY
Data sources: Datacite
versions View all 2 versions
addClaim

Computing Maximum Uniquely Restricted Matchings In Restricted Interval Graphs

Authors: Swapnil Gupta; C. Pandu Rangan;

Computing Maximum Uniquely Restricted Matchings In Restricted Interval Graphs

Abstract

{"references": ["Kathie Cameron. Induced matchings. Discrete Applied Mathematics,\n24(1):97\u2013102, 1989.", "Paul C Gilmore and Alan J Hoffman. A characterization of\ncomparability graphs and of interval graphs. Canad. J. Math,\n16(539-548):4, 1964.", "Martin Charles Golumbic. Algorithmic graph theory and perfect graphs,\nvolume 57. Elsevier, 2004.", "Martin Charles Golumbic, Tirza Hirst, and Moshe Lewenstein. Uniquely\nrestricted matchings. Algorithmica, 31(2):139\u2013154, 2001.", "Martin Charles Golumbic and Renu C Laskar. Irredundancy in circular\narc graphs. Discrete Applied Mathematics, 44(1):79\u201389, 1993.", "Martin Charles Golumbic and Moshe Lewenstein. New results on\ninduced matchings. Discrete Applied Mathematics, 101(1):157\u2013165,\n2000.", "Daniel Hershkowitz and Hans Schneider. Ranks of zero patterns and\nsign patterns. Linear and Multilinear Algebra, 34(1):3\u201319, 1993.", "Vadim E Levit and Eugen Mandrescu. Unicycle graphs and\nuniquely restricted maximum matchings. Electronic Notes in Discrete\nMathematics, 22:261\u2013265, 2005.", "Vadim E Levit and Eugen Mandrescu. On unicyclic graphs with\nuniquely restricted maximum matchings. Graphs and Combinatorics,\n29(6):1867\u20131879, 2013.\n[10] L\u00b4aszl\u00b4o Lov\u00b4asz and Michael D Plummer. Matching theory, volume 367.\nAmerican Mathematical Soc., 2009.\n[11] Lucia Draque Penso, Dieter Rautenbach, and Ueverton dos Santos\nSouza. Graphs in which some and every maximum matching is uniquely\nrestricted. arXiv preprint arXiv:1504.02250, 2015.\n[12] Guohun Zhu. Determining all maximum uniquely restricted matching\nin bipartite graphs. arXiv preprint arXiv:1009.5435, 2010."]}

A uniquely restricted matching is defined to be a matching M whose matched vertices induces a sub-graph which has only one perfect matching. In this paper, we make progress on the open question of the status of this problem on interval graphs (graphs obtained as the intersection graph of intervals on a line). We give an algorithm to compute maximum cardinality uniquely restricted matchings on certain sub-classes of interval graphs. We consider two sub-classes of interval graphs, the former contained in the latter, and give O(|E|^2) time algorithms for both of them. It is to be noted that both sub-classes are incomparable to proper interval graphs (graphs obtained as the intersection graph of intervals in which no interval completely contains another interval), on which the problem can be solved in polynomial time.

Keywords

interval graph, matching, design and analysis of algorithms, Uniquely restricted matching, witness counting., induced matching

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
    OpenAIRE UsageCounts
    Usage byUsageCounts
    visibility views 2
    download downloads 3
  • 2
    views
    3
    downloads
    Powered byOpenAIRE UsageCounts
Powered by OpenAIRE graph
Found an issue? Give us feedback
visibility
download
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
views
OpenAIRE UsageCountsViews provided by UsageCounts
downloads
OpenAIRE UsageCountsDownloads provided by UsageCounts
0
Average
Average
Average
2
3
Green