28 citations · 71 across the 13 of their papers we have counts for
Showing 2012Show all
2 papers · 1 filter
cs.DS2012
Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
Mark Jones, Daniel Lokshtanov, M. S. Ramanujan +2
We study the parameterized complexity of the directed variant of the classical {\sc Steiner Tree} problem on various classes of directed sparse graphs. While the parameterized comp…
cs.DS2012
Beyond Max-Cut: λ-Extendible Properties Parameterized Above the Poljak-Turzík Bound
Matthias Mnich, Geevarghese Philip, Saket Saurabh +1
Poljak and Turzík (Discrete Math. 1986) introduced the notion of λ-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any…