Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy

DOI10.1016/J.TCS.2012.01.025zbMath1253.68153arXiv1110.0187OpenAlexW2139428469MaRDI QIDQ690460

Yong Zhang, Ming-Hui Jiang

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

zbMATH Keywords

partitioncompletenessdominationseparationhardnessparameterized complexityirredundant set\(d\)-distance \(k\)-dominating set\(k\)-dominating setmultiple-interval graphsseparating vertices

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

The maximum clique problem in multiple interval graphs

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

This page was built for publication: Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy