TR-2012-11

Maximum negatable set in bipartite matching covered graphs

G. Sanjith



Abstract

In an undirected graph G=(V,E) with a conservative weighting w:E->{1, -1}, the problem of determining the maximum number of edges whose weight can be changed from 1 to -1 retaining the conservativeness of the weighting is known to be NP-complete. We show that this problem is polynomially tractable for bipartite matching-covered graphs. We also note that the directed version of this problem remains NP-complete for oriented bipartite matching-covered graphs.


Bibtex entry:

@techreport{egres-12-11,
AUTHOR = {Sanjith, G.},
TITLE = {Maximum negatable set in bipartite matching covered graphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2012},
NUMBER = {TR-2012-11}
}


Last modification: 5.12.2018. Please email your comments to Tamás Király!