171 citations
- Heriot-Watt UniversityGB4 papers
- Max Planck Institute for Gravitational PhysicsDE4 papers
- Centre National de la Recherche ScientifiqueFR3 papers
- Data61AU3 papers
- İzmir University of EconomicsTR3 papers
- Laboratoire d'Informatique, de Robotique et de Microélectronique de MontpellierFR3 papers
- UNSW SydneyAU3 papers
- Boston UniversityUS2 papers
- Cardiff UniversityGB2 papers
- Center for Astrophysics Harvard & SmithsonianUS2 papers
- Jagiellonian UniversityPL2 papers
- Lancaster UniversityGB2 papers
Showing 2008 · cs.DSShow all
2 papers · 2 filters
cs.DS2008
Minimum Leaf Out-branching and Related Problems
G. Gutin, I. Razgon, E. J. Kim
Given a digraph , the Minimum Leaf Out-Branching problem (MinLOB) is the problem of finding in an out-branching with the minimum possible number of leaves, i.e., vertices of…
cs.DS2008★ 4 cited
Almost 2-SAT is Fixed-Parameter Tractable
Igor Razgon, Barry O'Sullivan
We consider the following problem. Given a 2-CNF formula, is it possible to remove at most clauses so that the resulting 2-CNF formula is satisfiable? This problem is known to…