TY - GEN
T1 - On edge-independent sets
AU - Kloks, Ton
AU - Liu, Ching Hao
AU - Poon, Sheung Hung
N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.
PY - 2013
Y1 - 2013
N2 - A set of edges in a graph G is independent if no two elements are contained in a clique of G. The edge-independent set problem asks for the maximal cardinality of independent sets of edges. We show that the edge-clique graphs of cocktail parties have unbounded rankwidth. There is an elegant formula that solves the edge-independent set problem for graphs of rankwidth one, which are exactly distance-hereditary graphs, and related classes of graphs. We present a PTAS for the edge-independent set problem on planar graphs and show that the problem is polynomial for planar graphs without triangle separators. The set of edges of a bipartite graph is edge-independent. We show that the edge-independent set problem remains NP-complete for graphs in which every neighborhood is bipartite, i.e., the graphs without odd wheels.
AB - A set of edges in a graph G is independent if no two elements are contained in a clique of G. The edge-independent set problem asks for the maximal cardinality of independent sets of edges. We show that the edge-clique graphs of cocktail parties have unbounded rankwidth. There is an elegant formula that solves the edge-independent set problem for graphs of rankwidth one, which are exactly distance-hereditary graphs, and related classes of graphs. We present a PTAS for the edge-independent set problem on planar graphs and show that the problem is polynomial for planar graphs without triangle separators. The set of edges of a bipartite graph is edge-independent. We show that the edge-independent set problem remains NP-complete for graphs in which every neighborhood is bipartite, i.e., the graphs without odd wheels.
UR - http://www.scopus.com/inward/record.url?scp=84884844650&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-38756-2_28
DO - 10.1007/978-3-642-38756-2_28
M3 - Conference contribution
AN - SCOPUS:84884844650
SN - 9783642387555
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 272
EP - 283
BT - Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Third Joint International Conference, FAW-AAIM 2013, Proceedings
T2 - 7th International Frontiers in Algorithmics Workshop and the 9th International Conference on Algorithmic Aspects in Information and Management, FAW-AAIM 2013
Y2 - 26 June 2013 through 28 June 2013
ER -