Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
On multiway cut parameterized above lower bounds
View through CrossRef
We introduce a concept of parameterizing a problem above the optimum solution of its natural linear programming relaxation and prove that the
node multiway cut
problem is fixed-parameter tractable (FPT) in this setting. As a consequence we prove that node multiway cut is FPT, when parameterized above the maximum separating cut, resolving an open problem of Razgon.
Our results imply
O
*
(4
k
) algorithms for vertex cover above maximum matching and almost 2-SAT as well as an
O
*
(2
k
) algorithm for node multiway cut with a standard parameterization by the solution size, improving previous bounds for these problems.
Association for Computing Machinery (ACM)
Title: On multiway cut parameterized above lower bounds
Description:
We introduce a concept of parameterizing a problem above the optimum solution of its natural linear programming relaxation and prove that the
node multiway cut
problem is fixed-parameter tractable (FPT) in this setting.
As a consequence we prove that node multiway cut is FPT, when parameterized above the maximum separating cut, resolving an open problem of Razgon.
Our results imply
O
*
(4
k
) algorithms for vertex cover above maximum matching and almost 2-SAT as well as an
O
*
(2
k
) algorithm for node multiway cut with a standard parameterization by the solution size, improving previous bounds for these problems.
Related Results
Parameterized Strings: Algorithms and Applications
Parameterized Strings: Algorithms and Applications
The parameterized string (p-string), a generalization of the traditional string, is composed of constant and parameter symbols. A parameterized match (p-match) exists between two p...
ANALYSIS OF FACTORS INFLUENCING ADHERENCE TO ANTIRETROVIRAL MEDICATION (ARV) IN HIV/AIDS PATIENTS BASED ON INFORMATION, MOTIVATION, BEHAVIORAL SKILLS AT CUT MEUTIA GENERAL HOSPITAL
ANALYSIS OF FACTORS INFLUENCING ADHERENCE TO ANTIRETROVIRAL MEDICATION (ARV) IN HIV/AIDS PATIENTS BASED ON INFORMATION, MOTIVATION, BEHAVIORAL SKILLS AT CUT MEUTIA GENERAL HOSPITAL
HIV (Human Immunodeficiency Virus), included in the Retroviridae family, is a virus that causes AIDS (Acquired Immunodeficiency Syndrome), a syndrome caused by a decrease in the bo...
Multilinear Mathematical Separation in Chromatography
Multilinear Mathematical Separation in Chromatography
Chromatography is a powerful and generally applicable method for the analytical separation and quantification of the chemical constituents in complex mixtures because chromatograph...
Clique Cover and Graph Separation
Clique Cover and Graph Separation
The field of kernelization studies polynomial-time preprocessing routines for hard problems in the framework of parameterized complexity. In this article, we show that, unless the ...
The habitability of Earth-like (exo)planets: modelling and limitations.
The habitability of Earth-like (exo)planets: modelling and limitations.
Quick take: We investigate the conditions behind exoplanetary habitability. We compare how different models (complex physics-based vs. parameterized evolution) estimate the climate...
Homotopies in Multiway (Nondeterministic) Rewriting Systems as n-Fold Categories
Homotopies in Multiway (Nondeterministic) Rewriting Systems as n-Fold Categories
We investigate algebraic and compositional properties of abstract multiway rewriting systems, which are archetypical structures underlying the formalism of the Wolfram model. We de...
Subexponential lower bounds for f-ergodic Markov processes
Subexponential lower bounds for f-ergodic Markov processes
AbstractWe provide a criterion for establishing lower bounds on the rate of convergence in f-variation of a continuous-time ergodic Markov process to its invariant measure. The cri...
Multiway Sequential Cellular Automata
Multiway Sequential Cellular Automata
Cellular automata (CAs) are used to model rule-based evolutionary systems with standard CAs applying unitary, fixed rules to an entire generation at a time. A sequential updating a...