ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > FIXED-PARAMETER TRACTABLE ALGORITHMS:
Reports tagged with fixed-parameter tractable algorithms:
TR08-066 | 16th July 2008
Noga Alon, Shai Gutner

Kernels for the Dominating Set Problem on Graphs with an Excluded Minor

Revisions: 1
The domination number of a graph $G=(V,E)$ is the minimum size of a dominating set $U \subseteq V$, which satisfies that every vertex in $V \setminus U$ is adjacent to at least one vertex in $U$. The notion of a problem kernel refers to a polynomial time algorithm that achieves ... more >>>



ISSN 1433-8092 | Imprint