> Details

Fomin, Fedor V. [Author]; Golovach, Petr A. [Author]; Jaffke, Lars [Author]; Philip, Geevarghese [Author]; Sagunov, Danil [Author] ; Fedor V. Fomin and Petr A. Golovach and Lars Jaffke and Geevarghese Philip and Danil Sagunov [Contributor]

Diverse Pairs of Matchings

Reference
management

Bookmarks

Remove from
bookmarks

Share this on Whatsapp

Close

Bookmarks



You can manage bookmarks using lists, please log in to your user account for this.
  • Media type: E-Article; Electronic Conference Proceeding; Text
  • Title: Diverse Pairs of Matchings
  • Contributor: Fomin, Fedor V. [Author]; Golovach, Petr A. [Author]; Jaffke, Lars [Author]; Philip, Geevarghese [Author]; Sagunov, Danil [Author]
  • imprint: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020
  • Language: English
  • DOI: https://doi.org/10.4230/LIPIcs.ISAAC.2020.26
  • Keywords: Solution Diversity ; Fixed-Parameter Tractability ; Matching
  • Origination:
  • Footnote: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Description: We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph G and an integer k, ask whether G has two (maximum/perfect) matchings whose symmetric difference is at least k. Diverse Pair of Matchings (asking for two not necessarily maximum or perfect matchings) is NP-complete on general graphs if k is part of the input, and we consider two restricted variants. First, we show that on bipartite graphs, the problem is polynomial-time solvable, and second we show that Diverse Pair of Maximum Matchings is FPT parameterized by k. We round off the work by showing that Diverse Pair of Matchings has a kernel on 𝒪(k²) vertices.
  • Access State: Open Access