@InProceedings{hueffner14parameterized,
  author    = {Falk H{\"{u}}ffner and Christian Komusiewicz and Rolf Niedermeier and Martin R{\"{o}}tzschke},
  title     = {The Parameterized Complexity of the Rainbow Subgraph Problem},
  booktitle = {Proc. of Graph-Theoretic Concepts in Computer Science ({WG} 2014)},
  year      = {2014},
  editor    = {Dieter Kratsch and Ioan Todinca},
  volume    = {8747},
  series    = lncs,
  pages     = {287--298},
  publisher = Springer,
  abstract  = {The NP-hard Rainbow Subgraph problem, motivated from bioinformatics, is to find in an edge-colored graph a subgraph that contains each edge color exactly once and has at most k vertices. We examine the parameterized complexity of Rainbow Subgraph for paths, trees, and general graphs. We show, for example, APX-hardness even if the input graph is a properly edge-colored path in which every color occurs at most twice. Moreover, we show that Rainbow Subgraph is W[1]-hard with respect to the parameter k and also with respect to the dual parameter l := n - k where n is the number of vertices. Hence, we examine parameter combinations and show, for example, a polynomialsize problem kernel for the combined parameter l and "maximum number of colors incident with any vertex".},
  comment   = {brauche ich nur, um zu verdeutlichen, dass der Name Rainbow Subgraph problem (ZODIAC) schon weg ist},
  doi       = {10.1007/978-3-319-12340-0_24},
  keywords  = {rainbow subgraph problem; edge colored graph;},
  owner     = {Sebastian},
  timestamp = {2017.03.28},
}

{"_id":"nvsSH6NP5BSDbxg2L","bibbaseid":"hffner-komusiewicz-niedermeier-rtzschke-theparameterizedcomplexityoftherainbowsubgraphproblem-2014","authorIDs":[],"author_short":["Hüffner, F.","Komusiewicz, C.","Niedermeier, R.","Rötzschke, M."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Falk"],"propositions":[],"lastnames":["Hüffner"],"suffixes":[]},{"firstnames":["Christian"],"propositions":[],"lastnames":["Komusiewicz"],"suffixes":[]},{"firstnames":["Rolf"],"propositions":[],"lastnames":["Niedermeier"],"suffixes":[]},{"firstnames":["Martin"],"propositions":[],"lastnames":["Rötzschke"],"suffixes":[]}],"title":"The Parameterized Complexity of the Rainbow Subgraph Problem","booktitle":"Proc. of Graph-Theoretic Concepts in Computer Science (WG 2014)","year":"2014","editor":[{"firstnames":["Dieter"],"propositions":[],"lastnames":["Kratsch"],"suffixes":[]},{"firstnames":["Ioan"],"propositions":[],"lastnames":["Todinca"],"suffixes":[]}],"volume":"8747","series":"Lect Notes Comput Sci","pages":"287–298","publisher":"Springer, Berlin","abstract":"The NP-hard Rainbow Subgraph problem, motivated from bioinformatics, is to find in an edge-colored graph a subgraph that contains each edge color exactly once and has at most k vertices. We examine the parameterized complexity of Rainbow Subgraph for paths, trees, and general graphs. We show, for example, APX-hardness even if the input graph is a properly edge-colored path in which every color occurs at most twice. Moreover, we show that Rainbow Subgraph is W[1]-hard with respect to the parameter k and also with respect to the dual parameter l := n - k where n is the number of vertices. Hence, we examine parameter combinations and show, for example, a polynomialsize problem kernel for the combined parameter l and \"maximum number of colors incident with any vertex\".","comment":"brauche ich nur, um zu verdeutlichen, dass der Name Rainbow Subgraph problem (ZODIAC) schon weg ist","doi":"10.1007/978-3-319-12340-0_24","keywords":"rainbow subgraph problem; edge colored graph;","owner":"Sebastian","timestamp":"2017.03.28","bibtex":"@InProceedings{hueffner14parameterized,\n author = {Falk H{\\\"{u}}ffner and Christian Komusiewicz and Rolf Niedermeier and Martin R{\\\"{o}}tzschke},\n title = {The Parameterized Complexity of the Rainbow Subgraph Problem},\n booktitle = {Proc. of Graph-Theoretic Concepts in Computer Science ({WG} 2014)},\n year = {2014},\n editor = {Dieter Kratsch and Ioan Todinca},\n volume = {8747},\n series = lncs,\n pages = {287--298},\n publisher = Springer,\n abstract = {The NP-hard Rainbow Subgraph problem, motivated from bioinformatics, is to find in an edge-colored graph a subgraph that contains each edge color exactly once and has at most k vertices. We examine the parameterized complexity of Rainbow Subgraph for paths, trees, and general graphs. We show, for example, APX-hardness even if the input graph is a properly edge-colored path in which every color occurs at most twice. Moreover, we show that Rainbow Subgraph is W[1]-hard with respect to the parameter k and also with respect to the dual parameter l := n - k where n is the number of vertices. Hence, we examine parameter combinations and show, for example, a polynomialsize problem kernel for the combined parameter l and \"maximum number of colors incident with any vertex\".},\n comment = {brauche ich nur, um zu verdeutlichen, dass der Name Rainbow Subgraph problem (ZODIAC) schon weg ist},\n doi = {10.1007/978-3-319-12340-0_24},\n keywords = {rainbow subgraph problem; edge colored graph;},\n owner = {Sebastian},\n timestamp = {2017.03.28},\n}\n\n","author_short":["Hüffner, F.","Komusiewicz, C.","Niedermeier, R.","Rötzschke, M."],"editor_short":["Kratsch, D.","Todinca, I."],"key":"hueffner14parameterized","id":"hueffner14parameterized","bibbaseid":"hffner-komusiewicz-niedermeier-rtzschke-theparameterizedcomplexityoftherainbowsubgraphproblem-2014","role":"author","urls":{},"keyword":["rainbow subgraph problem; edge colored graph;"],"metadata":{"authorlinks":{}}},"bibtype":"inproceedings","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","creationDate":"2019-11-19T16:50:42.038Z","downloads":0,"keywords":["rainbow subgraph problem; edge colored graph;"],"search_terms":["parameterized","complexity","rainbow","subgraph","problem","hüffner","komusiewicz","niedermeier","rötzschke"],"title":"The Parameterized Complexity of the Rainbow Subgraph Problem","year":2014,"dataSources":["C5FtkvWWggFfMJTFX"]}