Faster algorithms for cograph edge modification problems

August 03, 2019 Β· Declared Dead Β· πŸ› Information Processing Letters

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Dekel Tsur arXiv ID 1908.01223 Category cs.DS: Data Structures & Algorithms Cross-listed cs.DM, math.CO Citations 5 Venue Information Processing Letters Last Checked 4 months ago
Abstract
In the Cograph Deletion (resp., Cograph Editing) problem the input is a graph $G$ and an integer $k$, and the goal is to decide whether there is a set of edges of size at most $k$ whose removal from $G$ (resp., removal and addition to $G$) results in a graph that does not contain an induced path with four vertices. In this paper we give algorithms for Cograph Deletion and Cograph Editing whose running times are $O^*(2.303^k)$ and $O^*(4.329^k)$, respectively.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted