We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Mod-2 Independence and Domination in Graphs.
- Authors
Halldórsson, Magnús M.; Kratochvíl, Jan; Telle, Jan Arne; Olariu, Stephan
- Abstract
We develop an O(n³) algorithm for deciding if an n-vertex digraph has a subset of vertices with the property that each vertex of the graph has an even number of arcs into the subset. This algorithm allows us to give a combinatorial interpretation of GaussJordan and Gauss elimination on square boolean matrices. In addition to solving this independence-mod-2 (even) set existence problem we also give efficient algorithms for related domination-mod-2 (odd) set existence problems on digraphs. However, for each of the four combinations of these two properties we show that even though the existence problem on digraphs is tractable, the problems of deciding the existence of a set of size exactly k, larger than k, or smaller than k, for a given k, are all NP-complete for undirected graphs.
- Subjects
ALGORITHMS; GRAPH theory; BOOLEAN algebra
- Publication
International Journal of Foundations of Computer Science, 2000, Vol 11, Issue 3, p355
- ISSN
0129-0541
- Publication type
Article