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)- Parameterized Complexity of Stabbing Rectangles and Squares in the Plane
- Incremental list coloring of graphs, parameterized by conservation
- On the \(k\)-colored rainbow sets in fixed dimensions
- On the Parameterized Complexity for Token Jumping on Graphs
- Parameterized complexity of three edge contraction problems with degree constraints
- Minimizing Rosenthal potential in multicast games
- On the parameterized complexity of computing balanced partitions in graphs
- On the parameterized complexity of finding separators with non-hereditary properties
- The parameterised complexity of counting connected subgraphs and graph motifs
- Subset feedback vertex set on graphs of bounded independent set size
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Kernel bounds for path and cycle problems
- The parameterised complexity of list problems on graphs of bounded treewidth
- On the complexity of some colorful problems parameterized by treewidth
- Tandem Duplications, Segmental Duplications and Deletions, and Their Applications
- The maximum clique problem in multiple interval graphs (extended abstract)
- CNF satisfiability in a subspace and related problems
- Multivariate complexity analysis of Swap Bribery
- Campaign management under approval-driven voting rules
- Enumerating homomorphisms
- Approximability and parameterized complexity of multicover by \(c\)-intervals
- Kernel bounds for path and cycle problems
- Planar capacitated dominating set is \(W[1]\)-hard
- Constant ratio fixed-parameter approximation of the edge multicut problem
- A refined complexity analysis of degree anonymization in graphs
- Towards a dichotomy for the possible winner problem in elections based on scoring rules
- Subset feedback vertex set on graphs of bounded independent set size
- Treewidth governs the complexity of target set selection
- Optimization problems in dotted interval graphs
- The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants
- On the complexity of the selective graph coloring problem in some special classes of graphs
- The parameterized complexity of local search for TSP, more refined
- Parameterized complexity in multiple-interval graphs: partition, separation, irredundancy
- Increasing the minimum degree of a graph by contractions
- Optimization problems in multiple-interval graphs
- On the parameterized complexity of some optimization problems related to multiple-interval graphs
- Parameterized algorithms for the independent set problem in some hereditary graph classes
- Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy
- On the parameterized complexity of some optimization problems related to multiple-interval graphs
- \(k\)-gap interval graphs
- Parameterized complexity of Eulerian deletion problems
- Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules
- Parameterized complexity of Min-power multicast problems in wireless ad hoc networks
- Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
- The maximum clique problem in multiple interval graphs
- The parameterized complexity of some minimum label problems
- Parameterized complexity in multiple-interval graphs: domination
- Designing FPT algorithms for cut problems using randomized contractions
- On the parameterised complexity of string morphism problems
- Shortest color-spanning intervals
- Parameterized complexity of critical node cuts
- The min-power multicast problems in wireless ad hoc networks: a parameterized view
- The parameterized complexity of the rainbow subgraph problem
- \(\mathrm{H}\)-index manipulation by merging articles: models, theory, and experiments
- Vertex Cover Reconfiguration and Beyond
- Editing graphs to satisfy degree constraints: a parameterized approach
- Parameterized complexity of finding small degree-constrained subgraphs
- Parameterized complexity of induced graph matching on claw-free graphs
- Optimization problems in multiple-interval graphs
- Stable matchings with covering constraints: a complete computational trichotomy
- Pure Nash equilibria in graphical games and treewidth
- Structural parameterizations of the mixed Chinese postman problem
- Deferred-query: An efficient approach for some problems on interval graphs
- Editing graphs into disjoint unions of dense clusters
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- Constant thresholds can make target set selection tractable
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- Algorithmic properties of sparse digraphs
- Parameterized complexity of voter control in multi-peaked elections
- A completeness theory for polynomial (Turing) kernelization
- Parameterized domination in circle graphs
- Algorithmic aspects of \textsc{Upper Domination}: a parameterised perspective
- Parameterized complexity of \((A,\ell)\)-path packing
- Mim-width. III. Graph powers and generalized distance domination problems
- Parameterized Complexity of $$(A,\ell )$$-Path Packing
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- Parameterized complexity of path set packing
- Succinct certification of monotone circuits
- Tractability, hardness, and kernelization lower bound for and/or graph solution
- A Parameterized Perspective on Attacking and Defending Elections
- The dominating set problem in geometric intersection graphs
- Length-bounded cuts: proper interval graphs and structural parameters
- Resolving conflicts for lower-bounded clustering
- Parameterized complexity of two-interval pattern problem
- A multistage view on 2-satisfiability
- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- Assessing the computational complexity of multi-layer subgraph detection
- Conflict free feedback vertex set: a parameterized dichotomy
- Mim-width. II. The feedback vertex set problem
- Solving partition problems almost always requires pushing many vertices around
- scientific article; zbMATH DE number 7378700 (Why is no real title available?)
- Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
- On some matching problems under the color-spanning model
- Finding temporal paths under waiting time constraints
- Parameterized complexity results for a model of theory of mind based on dynamic epistemic logic
- scientific article; zbMATH DE number 7378721 (Why is no real title available?)
- Connecting the dots (with minimum crossings)
- Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
- The many facets of upper domination
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)
