On the parameterized complexity of multiple-interval graph problems

From MaRDI portal

Publication:1001898

Jump to:navigation, search

DOI10.1016/j.tcs.2008.09.065zbMath1161.68038OpenAlexW2051627428WikidataQ57359825 ScholiaQ57359825MaRDI QIDQ1001898

Stéphane Vialette, Michael R. Fellows, Danny Hermelin, Frances A. 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

independent set clique dominating set parameterized complexity W-hardness multicolored clique multiple intervals

Mathematics Subject Classification ID

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

Related Items

Assessing the Computational Complexity of Multi-layer Subgraph Detection, Parameterized Complexity of $$(A,\ell )$$-Path Packing, A Parameterized Perspective on Attacking and Defending Elections, Tandem Duplications, Segmental Duplications and Deletions, and Their Applications, Consensus Patterns (Probably) Has no EPTAS, Structural Parameterizations of the Mixed Chinese Postman Problem, Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules, On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization), Designing FPT Algorithms for Cut Problems Using Randomized Contractions, New Results on Directed Edge Dominating Set, Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis, Grundy Distinguishes Treewidth from Pathwidth, Temporal interval cliques and independent sets, Parameterized algorithms and data reduction for the short secluded s‐t‐path problem, Parameterized complexity of path set packing, Recognizing when a preference system is close to admitting a master list, Recognizing when a preference system is close to admitting a master list, k-Efficient domination: Algorithmic perspective, The Parameterized Complexity of the Rectangle Stabbing Problem and Its Variants, Unnamed Item, Unnamed Item, An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Perfect domination and small cycles, Graph Motif Problems Parameterized by Dual, Unnamed Item, Unnamed Item, Parameterized Complexity of Directed Steiner Network with Respect to Shared Vertices and Arcs, On the Fixed-Parameter Tractability of Some Matching Problems Under the Color-Spanning Model, 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, Hitting and Piercing Rectangles Induced by a Point Set, Parameterized complexity of minimum membership dominating set, Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage, Unnamed Item, Multivariate Complexity Analysis of Swap Bribery, When can graph hyperbolicity be computed in linear time?, Parameterized Complexity of Stabbing Rectangles and Squares in the Plane, Hardness results for stable exchange problems, On Weisfeiler-Leman invariance: subgraph counts and related graph properties, The complexity of tree partitioning, Solving Partition Problems Almost Always Requires Pushing Many Vertices Around, On the tractability of covering a graph with 2-clubs, Connecting the dots (with minimum crossings), On the Parameterized Complexity of [1,j-Domination Problems], Planar Capacitated Dominating Set Is W[1-Hard], Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms, The Dominating Set Problem in Geometric Intersection Graphs, Length-bounded cuts: proper interval graphs and structural parameters, Possible winner problems on partial tournaments: a parameterized study, On Multiway Cut Parameterized above Lower Bounds, Parameterized Complexity in Multiple-Interval Graphs: Domination, Increasing the Minimum Degree of a Graph by Contractions, Kernel Bounds for Path and Cycle Problems, Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity, Parameterized complexity dichotomy for \textsc{Steiner Multicut}, Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes, On the parameterised complexity of string morphism problems, On the \(k\)-colored rainbow sets in fixed dimensions, \(\mathrm{H}\)-index manipulation by merging articles: models, theory, and experiments, Parameterized complexity of minimum membership dominating set, The parameterised complexity of list problems on graphs of bounded treewidth, Parameterized complexity of the MinCCA problem on graphs of bounded decomposability, Parameterized complexity of fair deletion problems, On independent set in \(B_1\)-EPG graphs, Parameterized complexity of secluded connectivity problems, The parameterized complexity of local search for TSP, more refined, On the parameterized complexity of some optimization problems related to multiple-interval graphs, Tractability, hardness, and kernelization lower bound for and/or graph solution, Vertex Cover Reconfiguration and Beyond, 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, Shortest color-spanning intervals, Parameterized complexity of happy coloring problems, The challenges of unbounded treewidth in parameterised subgraph counting problems, Parameterized complexity of finding small degree-constrained subgraphs, Editing graphs to satisfy degree constraints: a parameterized approach, Enumerating homomorphisms, On the complexity of some colorful problems parameterized by treewidth, On the tractability of optimization problems on \(H\)-graphs, The parameterized complexity of stabbing rectangles, A multistage view on 2-satisfiability, The many facets of upper domination, The P3 infection time is W[1-hard parameterized by the treewidth], Reconfiguration of cliques in a graph, The complexity of routing problems in forbidden-transition graphs and edge-colored graphs, Parameterized complexity of theory of mind reasoning in dynamic epistemic logic, Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number, Parameterized domination in circle graphs, Parameterized complexity of Eulerian deletion problems, The parameterized complexity of some minimum label problems, Towards a dichotomy for the possible winner problem in elections based on scoring rules, Paths of bounded length and their cuts: parameterized complexity and algorithms, Treewidth governs the complexity of target set selection, Editing graphs into disjoint unions of dense clusters, Parameterized complexity of three edge contraction problems with degree constraints, Parameterized dynamic cluster editing, On the complexity of the selective graph coloring problem in some special classes of graphs, Parameterized complexity of induced graph matching on claw-free graphs, The parameterized complexity of the rainbow subgraph problem, Dispersing and grouping points on planar segments, Succinct certification of monotone circuits, Finding supported paths in heterogeneous networks, The complexity of dominating set in geometric intersection graphs, On the parameterized complexity of computing balanced partitions in graphs, Minimizing Rosenthal potential in multicast games, On the parameterized complexity of finding separators with non-hereditary properties, Finding temporal paths under waiting time constraints, Campaign management under approval-driven voting rules, Parameterized complexity of critical node cuts, The complexity of finding effectors, 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, Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy, Parameterizing by the number of numbers, Constant thresholds can make target set selection tractable, Multivariate complexity analysis of Swap Bribery, The parameterised complexity of counting connected subgraphs and graph motifs, Minimum diameter color-spanning sets revisited, Succinct monotone circuit certification: planarity and parameterized complexity, Constant ratio fixed-parameter approximation of the edge multicut problem, New algorithms for maximum disjoint paths based on tree-likeness, On the parameterized complexity of \([1,j\)-domination problems], Mim-width. II. The feedback vertex set problem, Efficiently enumerating hitting sets of hypergraphs arising in data profiling, Subset feedback vertex set on graphs of bounded independent set size, Stable matchings with covering constraints: a complete computational trichotomy, Upper and lower degree-constrained graph orientation with minimum penalty, Algorithmic Aspects of Upper Domination: A Parameterised Perspective, Parameterized complexity of two-interval pattern problem, Some Hard Families of Parameterized Counting Problems, On some matching problems under the color-spanning model, Exact multi-covering problems with geometric sets, 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, CNF satisfiability in a subspace and related problems, On structural parameterizations for the 2-club problem, 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, Parameterized complexity of \((A,\ell)\)-path packing

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1001898&oldid=12992791"