On the parameterized complexity of multiple-interval graph problems
From MaRDI portal
dominating setcliqueindependent setparameterized complexityW-hardnessmulticolored cliquemultiple intervals
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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)
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
- 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?)
- 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]
- 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)- Kernel bounds for path and cycle problems
- Parameterized complexity results for a model of theory of mind based on dynamic epistemic logic
- Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
- A multistage view on 2-satisfiability
- The parameterized complexity of the minimum shared edges problem
- On the parameterized complexity of \([1,j]\)-domination problems
- Consensus patterns (probably) has no EPTAS
- Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules
- The multicolored graph realization problem
- Optimization problems in dotted interval graphs
- Parameterized complexity of voter control in multi-peaked elections
- On treewidth and stable marriage: parameterized algorithms and hardness results (complete characterization)
- Mim-width. III. Graph powers and generalized distance domination problems
- Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy
- Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
- The parameterized complexity of the rainbow subgraph problem
- Parameterized domination in circle graphs
- Generalized distance domination problems and their complexity on graphs of bounded mim-width
- Grundy Distinguishes Treewidth from Pathwidth
- Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
- Designing FPT algorithms for cut problems using randomized contractions
- Assessing the computational complexity of multi-layer subgraph detection
- Treewidth governs the complexity of target set selection
- The parameterized complexity of stabbing rectangles
- On the parameterized complexity of interval scheduling with eligible machine sets
- A Parameterized Perspective on Attacking and Defending Elections
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- When can graph hyperbolicity be computed in linear time?
- Incremental list coloring of graphs, parameterized by conservation
- Finding supported paths in heterogeneous networks
- The complexity of dominating set in geometric intersection graphs
- Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis
- Enumerating homomorphisms
- Perfect domination and small cycles
- Parameterized Complexity of $$(A,\ell )$$-Path Packing
- Constant thresholds can make target set selection tractable
- On Weisfeiler-Leman invariance: subgraph counts and related graph properties
- Editing graphs into disjoint unions of dense clusters
- The dominating set problem in geometric intersection graphs
- Minimum diameter color-spanning sets revisited
- Some hard families of parameterized counting problems
- Connecting the dots (with minimum crossings)
- Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
- Dispersing and grouping points on planar segments
- Planar capacitated dominating set is \(W[1]\)-hard
- The min-power multicast problems in wireless ad hoc networks: a parameterized view
- Parameterized Complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs
- Succinct monotone circuit certification: planarity and parameterized complexity
- On the complexity of finding and counting solution-free sets of integers
- Parameterized complexity in multiple-interval graphs: domination
- Temporal interval cliques and independent sets
- On the fixed-parameter tractability of some matching problems under the color-spanning model
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- Parameterized complexity of Eulerian deletion problems
- CNF satisfiability in a subspace and related problems
- Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
- Shortest color-spanning intervals
- Editing graphs to satisfy degree constraints: a parameterized approach
- The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
- scientific article; zbMATH DE number 7765417 (Why is no real title available?)
- \(k\)-gap interval graphs
- Multivariate complexity analysis of swap bribery
- Stable matchings with covering constraints: a complete computational trichotomy
- Approximability and parameterized complexity of multicover by \(c\)-intervals
- Deferred-query: An efficient approach for some problems on interval graphs
- On some matching problems under the color-spanning model
- Parameterized dynamic cluster editing
- On the parameterized complexity of some optimization problems related to multiple-interval graphs
- Tractability, hardness, and kernelization lower bound for and/or graph solution
- Mim-width. II. The feedback vertex set problem
- The parameterised complexity of counting connected subgraphs and graph motifs
- On the parameterised complexity of string morphism problems
- The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants
- On the parameterized complexity of some optimization problems related to multiple-interval graphs
- scientific article; zbMATH DE number 7378700 (Why is no real title available?)
- Solving partition problems almost always requires pushing many vertices around
- scientific article; zbMATH DE number 7378721 (Why is no real title available?)
- Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
- Hitting and Piercing Rectangles Induced by a Point Set
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- Campaign management under approval-driven voting rules
- The complexity of computing optimum labelings for temporal connectivity
- Constant ratio fixed-parameter approximation of the edge multicut problem
- Parameterized problems complete for nondeterministic FPT time and logarithmic space
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- On parameterized complexity of the multi-MCS problem
- \(\mathrm{H}\)-index manipulation by merging articles: models, theory, and experiments
- Parameterized complexity of minimum membership dominating set
- New algorithms for maximum disjoint paths based on tree-likeness
- On the tractability of optimization problems on \(H\)-graphs
- Parameterized complexity of secluded connectivity problems
- Subset feedback vertex set on graphs of bounded independent set size
- Succinct certification of monotone circuits
- Parameterized complexity of minimum membership dominating set
- Algorithmic properties of sparse digraphs
- Parameterized complexity of three edge contraction problems with degree constraints
- Subset feedback vertex set on graphs of bounded independent set size
- Parameterized complexity of two-interval pattern problem
- Algorithmic aspects of \textsc{Upper Domination}: a parameterised perspective
- On the complexity of the selective graph coloring problem in some special classes of graphs
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)
