In: Discrete Mathematics, 2010, vol. 310, p. 132-146
Given an undirected graph G=(V,E) with matching number \nu(G), a d-blocker is a subset of edges B such that \nu(/V,E\B))= d. While the associated decision problem is NP-complete in bipartite graphs we show how to construct efficiently minimum d-transversals and minimum d-blockers in the...
|
In: Journal of Discrete Algorithms, 2012, vol. 17, p. 95-102
Let G = (V , E) be a graph in which every vertex v ∈ V has a weight w(v)>=0 and a cost c(v) >=0. Let SG be the family of all maximum-weight stable sets in G. For any integer d 0, a minimum d-transversal in the graph G with respect to SG is a subset of vertices T ⊆ V of minimum total cost such that |T ∩ S| d for every S ∈ SG. In this paper, we present a polynomial-time algorithm to...
|
In: Discrete Applied Mathematics, 2010, vol. 158, no. 5, p. 592-596
In this note we consider two coloring problems in mixed graphs, i.e., graphs containing edges and arcs, which arise from scheduling problems where disjunctive and precedence constraints have to be taken into account. We show that they are both NP-complete in cubic planar bipartite mixed graphs, which strengthens some results of Ries and de Werra (2008) [9].
|
