On the parameterized complexity of multiple-interval graph problems

DOI10.1016/J.TCS.2008.09.065MaRDI QIDQ1001898zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Michael R. Fellows, Danny Hermelin, Stéphane Vialette, Frances Rosamond

Publication date 19 February 2009

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2008.09.065

zbMATH Keywords

cliquedominating setindependent setmulticolored cliquemultiple intervalsparameterized complexityW-hardness

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy
• Parameterized complexity in multiple-interval graphs: domination
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• Parameterized complexity in multiple-interval graphs: partition, separation, irredundancy

Cites work

• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Algorithms – ESA 2005
• Algorithms – ESA 2005
• Algorithms – ESA 2005
• Approximation algorithms for hitting objects with straight lines
• Color-coding
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
• Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms
• Domination, independent domination, and duality in strongly chordal graphs
• Dotted interval graphs and high throughput genotyping
• Experimental and Efficient Algorithms
• Extracting constrained 2-interval subsets in 2-interval sets
• Extremal Values of the Interval Number of a Graph
• Extremal values of the interval number of a graph, II
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 1185295 (Why is no real title available?)
• scientific article; zbMATH DE number 125608 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 1754598 (Why is no real title available?)
• scientific article; zbMATH DE number 2119734 (Why is no real title available?)
• scientific article; zbMATH DE number 806748 (Why is no real title available?)
• Improved complexity bounds for location problems on the real line
• Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
• On the parameterized complexity of short computation and factorization
• Optimization problems in multiple-interval graphs
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Recognizing graphs with fixed interval number is NP-complete
• The interval number of a planar graph: Three intervals suffice

Cited in

(only showing first 100 items - show all)

• On parameterized complexity of the multi-MCS problem
• The many facets of upper domination
• The P3 infection time is W[1]-hard parameterized by the treewidth
• Parameterized complexity of theory of mind reasoning in dynamic epistemic logic
• The parameterized complexity of the rainbow subgraph problem
• Finding supported paths in heterogeneous networks
• The complexity of dominating set in geometric intersection graphs
• On the complexity of finding and counting solution-free sets of integers
• The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
• Multivariate complexity analysis of Swap Bribery
• New algorithms for maximum disjoint paths based on tree-likeness
• The parameterized complexity of some minimum label problems
• Towards a dichotomy for the possible winner problem in elections based on scoring rules
• Finding temporal paths under waiting time constraints
• Minimum diameter color-spanning sets revisited
• Succinct monotone circuit certification: planarity and parameterized complexity
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• Upper and lower degree-constrained graph orientation with minimum penalty
• Parameterized complexity of two-interval pattern problem
• Exact multi-covering problems with geometric sets
• CNF satisfiability in a subspace and related problems
• Parameterized complexity of \((A,\ell)\)-path packing
• Length-bounded cuts: proper interval graphs and structural parameters
• Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
• Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
• On the \(k\)-colored rainbow sets in fixed dimensions
• Parameterized complexity of minimum membership dominating set
• On independent set in \(B_1\)-EPG graphs
• Parameterized complexity of happy coloring problems
• On the tractability of optimization problems on \(H\)-graphs
• Parameterized dynamic cluster editing
• Dispersing and grouping points on planar segments
• Succinct certification of monotone circuits
• Constant thresholds can make target set selection tractable
• The parameterised complexity of counting connected subgraphs and graph motifs
• On the parameterized complexity of \([1,j]\)-domination problems
• Mim-width. II. The feedback vertex set problem
• Subset feedback vertex set on graphs of bounded independent set size
• Stable matchings with covering constraints: a complete computational trichotomy
• On some matching problems under the color-spanning model
• Parameterized complexity of voter control in multi-peaked elections
• The parameterized complexity of the minimum shared edges problem
• Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
• Mim-width. III. Graph powers and generalized distance domination problems
• A completeness theory for polynomial (Turing) kernelization
• Pure Nash equilibria in graphical games and treewidth
• A refined complexity analysis of degree anonymization in graphs
• Approximability and parameterized complexity of multicover by \(c\)-intervals
• The maximum clique problem in multiple interval graphs
• Possible winner problems on partial tournaments: a parameterized study
• Parameterized complexity of secluded connectivity problems
• Tractability, hardness, and kernelization lower bound for and/or graph solution
• The parameterized complexity of stabbing rectangles
• Parameterized domination in circle graphs
• Parameterized complexity of Eulerian deletion problems
• On the complexity of the selective graph coloring problem in some special classes of graphs
• A multistage view on 2-satisfiability
• Reconfiguration of cliques in a graph
• The complexity of routing problems in forbidden-transition graphs and edge-colored graphs
• Algorithmic aspects of \textsc{Upper Domination}: a parameterised perspective
• Some hard families of parameterized counting problems
• Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization
• Parameterized complexity in multiple-interval graphs: domination
• Increasing the minimum degree of a graph by contractions
• Kernel bounds for path and cycle problems
• k-gap interval graphs
• Optimization problems in multiple-interval graphs
• Optimization problems in multiple-interval graphs
• Vertex Cover Reconfiguration and Beyond
• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• Parameterized algorithms for the independent set problem in some hereditary graph classes
• The min-power multicast problems in wireless ad hoc networks: a parameterized view
• Multivariate complexity analysis of swap bribery
• Parameterized complexity in multiple-interval graphs: partition, separation, irredundancy
• On the parameterised complexity of string morphism problems
• Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules
• Designing FPT algorithms for cut problems using randomized contractions
• \(\mathrm{H}\)-index manipulation by merging articles: models, theory, and experiments
• The parameterised complexity of list problems on graphs of bounded treewidth
• Consensus patterns (probably) has no EPTAS
• Structural parameterizations of the mixed Chinese postman problem
• The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
• Planar capacitated dominating set is \(W[1]\)-hard
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• The parameterized complexity of local search for TSP, more refined
• Increasing the minimum degree of a graph by contractions
• Parameterized complexity of Min-power multicast problems in wireless ad hoc networks
• Incremental list coloring of graphs, parameterized by conservation
• Kernel bounds for path and cycle problems
• Optimization problems in dotted interval graphs
• Parameterized complexity of finding small degree-constrained subgraphs
• Editing graphs to satisfy degree constraints: a parameterized approach
• Enumerating homomorphisms
• Deferred-query: An efficient approach for some problems on interval graphs
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• Treewidth governs the complexity of target set selection

This page was built for publication: On the parameterized complexity of multiple-interval graph problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1001898)