Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy
From MaRDI portal
Publication:690460
DOI10.1016/j.tcs.2012.01.025zbMath1253.68153arXiv1110.0187MaRDI QIDQ690460
Publication date: 27 November 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1110.0187
partition; completeness; domination; separation; hardness; parameterized complexity; irredundant set; \(d\)-distance \(k\)-dominating set; \(k\)-dominating set; multiple-interval graphs; separating vertices
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the parameterized complexity of some optimization problems related to multiple-interval graphs
- Dominating set is fixed parameter tractable in claw-free graphs
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- On the parameterized complexity of multiple-interval graph problems
- On recovering syntenic blocks from comparative maps
- Extremal values of the interval number of a graph, II
- Some simplified NP-complete graph problems
- On the parameterized complexity of short computation and factorization
- Perfect Code is \(W[1\)-complete]
- The complexity of irredundant sets parameterized by size
- Parameterized Complexity in Multiple-Interval Graphs: Domination
- Optimization problems in multiple-interval graphs
- Parameterized Complexity in Multiple-Interval Graphs: Partition, Separation, Irredundancy
- Parameterized Complexity of Independence and Domination on Geometric Graphs
- The Complexity of Coloring Circular Arcs and Chords
- Parameterized and Exact Computation
- Data reduction and exact algorithms for clique cover
- Scheduling Split Intervals
