Raman, Venkatesh ; Saurabh, Saket (2007) Improved fixed parameter tractable algorithms for two “edge” problems: MAXCUT and MAXDAG Information Processing Letters, 104 (2). pp. 65-72. ISSN 0020-0190
Full text not available from this repository.
Official URL: http://doi.org/10.1016/j.ipl.2007.05.014
Related URL: http://dx.doi.org/10.1016/j.ipl.2007.05.014
Abstract
We give improved parameterized algorithms for two “edge” problems MAXCUT and MAXDAG, where the solution sought is a subset of edges. MAXCUT of a graph is a maximum set of edges forming a bipartite subgraph of the given graph. On the other hand, MAXDAG of a directed graph is a set of arcs of maximum size such that the graph induced on these arcs is acyclic. Our algorithms are obtained through new kernelization and efficient exact algorithms for the optimization versions of the problems.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| ID Code: | 123480 |
| Deposited On: | 20 Sep 2021 11:03 |
| Last Modified: | 20 Sep 2021 11:03 |
Repository Staff Only: item control page
