Loading...
Please wait, while we are loading the content...
The Labeled perfect matching in bipartite graphs : complexity and ( in ) approximability
| Content Provider | Semantic Scholar |
|---|---|
| Copyright Year | 2007 |
| Abstract | Let Π be a NPO problem accepting simple graphs G = (V,E) as instances, edgesubsets E ⊆ E satisfying a given polynomial-time decidable property Pred as solutions, and the solutions cardinality as objective function ; the labeled problem associated to Π, denoted by LABELED Π, seeks, given an instance I = (G,L) where G = (V,E) is a simple graph and L is a mapping from E to {c1, . . . , cq}, in finding a subset E satisfying Pred that optimizes the size of the set L(E) = {L(e) : e ∈ E′}. Note that two versions of LABELED Π may be considered according to the optimization goal : LABELED Min Π that consists in minimizing |L(E′)| and LABELED Max Π that consists in maximizing |L(E′)|. Roughly speaking, the mapping L corresponds to assigning a color (or a label) to each edge and the goal of LABELED Min Π (resp., Max Π) is to find an edge subset using the fewest (resp., the most) number of colors. If a given NPO problem Π is NP-hard, then the associated labeled problem LABELED Π is clearly NP-hard (consider a distinct color per edge). For instance, the LABELED Longest path problem or the LABELED maximum induced matching problem are both NP-hard. Moreover, if the decision problem derived from Π where one aims at deciding if a graph G contains an edge subset satisfying Pred |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.lamsade.dauphine.fr/~monnot/index_fichiers/chap/Wiley-ISTE_LabeledMatching.pdf |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Approximation algorithm Cardinality Color Decision problem Graph (discrete mathematics) Graph - visual representation Longest path problem Loss function Matching (graph theory) Mathematical optimization NP-hardness Nonprofit Organizations Optimization problem Polynomial Solutions Speaking (activity) Subgroup Time complexity Tracer Version |
| Content Type | Text |
| Resource Type | Article |
