Inductive $k$-independent graphs and $c$-colorable subgraphs in scheduling: A review. Bentert, M., van Bevern, R., & Niedermeier, R. Journal of Scheduling, 22(1):3–20, 2019. ![Inductive $k$-independent graphs and $c$-colorable subgraphs in scheduling: A review [link]](https://bibbase.org/img/filetypes/link.svg "link")
Preprint Poster doi abstract bibtex Inductive k-independent graphs generalize chordal graphs and have recently been advocated in the context of interference-avoiding wireless communication scheduling. The NP-hard problem of finding maximum-weight induced c-colorable subgraphs, which is a generalization of finding maximum independent sets, naturally occurs when selecting c sets of pairwise non-conflicting jobs (modeled as graph vertices). We investigate the parameterized complexity of this problem on inductive k-independent graphs. We show that the Independent Set problem is W[1]-hard even on 2-simplicial 3-minoes—a subclass of inductive 2-independent graphs. In contrast, we prove that the more general Maximum c-Colorable Subgraph problem is fixed-parameter tractable on edge-wise unions of cluster and chordal graphs, which are 2-simplicial. In both cases, the parameter is the solution size. Aside from this, we survey other graph classes between inductive 1-inductive and inductive 2-inductive graphs with applications in scheduling.
@article{BBN19,
author = {Matthias Bentert and Ren{\'{e}} van Bevern and Rolf
Niedermeier},
journal = {Journal of Scheduling},
date = {2019-02-01},
title = {Inductive $k$-independent graphs and $c$-colorable
subgraphs in scheduling: A review},
year = 2019,
doi = {10.1007/s10951-018-0595-8},
volume = {22},
number = 1,
pages = {3--20},
url_Preprint = {https://arxiv.org/abs/1712.06481},
url_Poster =
{https://www.researchgate.net/publication/342122158_Wireless_Scheduling_Graph_Classes_and_c-Colorable_Subgraphs},
abstract = {Inductive k-independent graphs generalize chordal
graphs and have recently been advocated in the
context of interference-avoiding wireless
communication scheduling. The NP-hard problem of
finding maximum-weight induced c-colorable
subgraphs, which is a generalization of finding
maximum independent sets, naturally occurs when
selecting c sets of pairwise non-conflicting jobs
(modeled as graph vertices). We investigate the
parameterized complexity of this problem on
inductive k-independent graphs. We show that the
Independent Set problem is W[1]-hard even on
2-simplicial 3-minoes---a subclass of inductive
2-independent graphs. In contrast, we prove that the
more general Maximum c-Colorable Subgraph problem is
fixed-parameter tractable on edge-wise unions of
cluster and chordal graphs, which are
2-simplicial. In both cases, the parameter is the
solution size. Aside from this, we survey other
graph classes between inductive 1-inductive and
inductive 2-inductive graphs with applications in
scheduling.}
}
Downloads: 0
{"_id":"s4Pp52kMjQyCrY65K","bibbaseid":"bentert-vanbevern-niedermeier-inductivekindependentgraphsandccolorablesubgraphsinschedulingareview-2019","authorIDs":["2fwXJtKDCNhaSNr5s"],"author_short":["Bentert, M.","van Bevern, R.","Niedermeier, R."],"bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["Matthias"],"propositions":[],"lastnames":["Bentert"],"suffixes":[]},{"firstnames":["René"],"propositions":["van"],"lastnames":["Bevern"],"suffixes":[]},{"firstnames":["Rolf"],"propositions":[],"lastnames":["Niedermeier"],"suffixes":[]}],"journal":"Journal of Scheduling","date":"2019-02-01","title":"Inductive $k$-independent graphs and $c$-colorable subgraphs in scheduling: A review","year":"2019","doi":"10.1007/s10951-018-0595-8","volume":"22","number":"1","pages":"3–20","url_preprint":"https://arxiv.org/abs/1712.06481","url_poster":"https://www.researchgate.net/publication/342122158_Wireless_Scheduling_Graph_Classes_and_c-Colorable_Subgraphs","abstract":"Inductive k-independent graphs generalize chordal graphs and have recently been advocated in the context of interference-avoiding wireless communication scheduling. The NP-hard problem of finding maximum-weight induced c-colorable subgraphs, which is a generalization of finding maximum independent sets, naturally occurs when selecting c sets of pairwise non-conflicting jobs (modeled as graph vertices). We investigate the parameterized complexity of this problem on inductive k-independent graphs. We show that the Independent Set problem is W[1]-hard even on 2-simplicial 3-minoes—a subclass of inductive 2-independent graphs. In contrast, we prove that the more general Maximum c-Colorable Subgraph problem is fixed-parameter tractable on edge-wise unions of cluster and chordal graphs, which are 2-simplicial. In both cases, the parameter is the solution size. Aside from this, we survey other graph classes between inductive 1-inductive and inductive 2-inductive graphs with applications in scheduling.","bibtex":"@article{BBN19,\n author =\t {Matthias Bentert and Ren{\\'{e}} van Bevern and Rolf\n Niedermeier},\n journal =\t {Journal of Scheduling},\n date =\t {2019-02-01},\n title =\t {Inductive $k$-independent graphs and $c$-colorable\n subgraphs in scheduling: A review},\n year =\t 2019,\n doi =\t\t {10.1007/s10951-018-0595-8},\n volume =\t {22},\n number =\t 1,\n pages =\t {3--20},\n url_Preprint = {https://arxiv.org/abs/1712.06481},\n url_Poster =\n {https://www.researchgate.net/publication/342122158_Wireless_Scheduling_Graph_Classes_and_c-Colorable_Subgraphs},\n abstract =\t {Inductive k-independent graphs generalize chordal\n graphs and have recently been advocated in the\n context of interference-avoiding wireless\n communication scheduling. The NP-hard problem of\n finding maximum-weight induced c-colorable\n subgraphs, which is a generalization of finding\n maximum independent sets, naturally occurs when\n selecting c sets of pairwise non-conflicting jobs\n (modeled as graph vertices). We investigate the\n parameterized complexity of this problem on\n inductive k-independent graphs. We show that the\n Independent Set problem is W[1]-hard even on\n 2-simplicial 3-minoes---a subclass of inductive\n 2-independent graphs. In contrast, we prove that the\n more general Maximum c-Colorable Subgraph problem is\n fixed-parameter tractable on edge-wise unions of\n cluster and chordal graphs, which are\n 2-simplicial. In both cases, the parameter is the\n solution size. Aside from this, we survey other\n graph classes between inductive 1-inductive and\n inductive 2-inductive graphs with applications in\n scheduling.}\n}\n\n\n","author_short":["Bentert, M.","van Bevern, R.","Niedermeier, R."],"key":"BBN19","id":"BBN19","bibbaseid":"bentert-vanbevern-niedermeier-inductivekindependentgraphsandccolorablesubgraphsinschedulingareview-2019","role":"author","urls":{" preprint":"https://arxiv.org/abs/1712.06481"," poster":"https://www.researchgate.net/publication/342122158_Wireless_Scheduling_Graph_Classes_and_c-Colorable_Subgraphs"},"metadata":{"authorlinks":{"van bevern, r":"https://rvb.su/"}},"downloads":0,"html":""},"bibtype":"article","biburl":"http://rvb.su/rvb.bib","creationDate":"2021-01-06T14:16:51.463Z","downloads":0,"keywords":[],"search_terms":["inductive","independent","graphs","colorable","subgraphs","scheduling","review","bentert","van bevern","niedermeier"],"title":"Inductive $k$-independent graphs and $c$-colorable subgraphs in scheduling: A review","year":2019,"dataSources":["G5GefJqqu2DtnCZXz"]}