Algorithms for Vertex Partitioning Problems on Partial k-Trees
From MaRDI portal
Publication:4377448
DOI10.1137/S0895480194275825zbMath0885.68118OpenAlexW2067264828WikidataQ29301396 ScholiaQ29301396MaRDI QIDQ4377448
Andrzej Proskurowski, Jan Arne Telle
Publication date: 9 February 1998
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0895480194275825
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (only showing first 100 items - show all)
Algorithms for vertex-partitioning problems on graphs with fixed clique-width. ⋮ Star colouring of bounded degree graphs and regular graphs ⋮ Graph separators: A parameterized view ⋮ Weighted restrained domination in subclasses of planar graphs ⋮ Equality in a bound that relates the size and the restrained domination number of a graph ⋮ Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ Fast Algorithms for Join Operations on Tree Decompositions ⋮ Parameterized power domination complexity ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Restrained and total restrained domination in cographs ⋮ Results on the Grundy chromatic number of graphs ⋮ List homomorphisms of graphs with bounded degrees ⋮ An upper bound for the total restrained domination number of graphs ⋮ Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs ⋮ The \(k\)-path coloring problem in graphs of bounded treewidth: an application in integrated circuit manufacturing ⋮ Mim-width. I. Induced path problems ⋮ Total restrained domination in trees ⋮ An improved upper bound on the total restrained domination number in cubic graphs ⋮ MSOL partitioning problems on graphs of bounded treewidth and clique-width ⋮ Restrained domination in some subclasses of chordal graphs ⋮ On the Grundy number of Cameron graphs ⋮ A width parameter useful for chordal and co-comparability graphs ⋮ Certifying coloring algorithms for graphs without long induced paths ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems ⋮ Splitting trees at vertices ⋮ Structure and algorithms for (cap, even hole)-free graphs ⋮ When an optimal dominating set with given constraints exists ⋮ Fast exact algorithms for some connectivity problems parameterized by clique-width ⋮ Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity ⋮ Courcelle's theorem -- a game-theoretic approach ⋮ Structural parameters, tight bounds, and approximation for \((k, r)\)-center ⋮ Total restrained domination in claw-free graphs with minimum degree at least two ⋮ On the complexity of the bondage and reinforcement problems ⋮ Parameterized complexity of generalized domination problems ⋮ Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs ⋮ How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms ⋮ On b-acyclic chromatic number of a graph ⋮ Exact algorithms for edge domination ⋮ Grundy coloring in some subclasses of bipartite graphs and their complements ⋮ Unnamed Item ⋮ The restrained domination and independent restrained domination in extending supergrid graphs ⋮ NP-completeness and APX-completeness of restrained domination in graphs ⋮ Restrained domination and its variants in extended supergrid graphs ⋮ On the equality of the partial Grundy and upper ochromatic numbers of graphs ⋮ On bondage numbers of graphs: a survey with some comments ⋮ Grundy Coloring and friends, half-graphs, bicliques ⋮ Output-polynomial enumeration on graphs of bounded (local) linear MIM-width ⋮ Algorithmic aspect of stratified domination in graphs ⋮ Faster algorithms for vertex partitioning problems parameterized by clique-width ⋮ Iterated colorings of graphs. ⋮ The product of the restrained domination numbers of a graph and its complement ⋮ On roman, global and restrained domination in graphs ⋮ Restrained domination in self-complementary graphs ⋮ Total restrained domination in graphs ⋮ On a conjecture involving a bound for the total restrained domination number of a graph ⋮ Minimum order of graphs with given coloring parameters ⋮ On equality in an upper bound for the restrained and total domination numbers of a graph ⋮ Computing the Chromatic Number Using Graph Decompositions via Matrix Rank ⋮ Restrained bondage number of a graph ⋮ (Total) domination in prisms ⋮ Total restrained domination in graphs with minimum degree two ⋮ Characterizations of trees with equal domination parameters ⋮ Complexity of Grundy coloring and its variants ⋮ Improved algorithms and complexity results for power domination in graphs ⋮ \(F_3\)-domination problem of graphs ⋮ Treewidth computations. I: Upper bounds ⋮ On the Grundy number of graphs with few \(P_4\)'s ⋮ Partitioning graphs of supply and demand ⋮ Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm ⋮ An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree ⋮ Restrained domination in claw-free graphs with minimum degree at least two ⋮ Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs ⋮ Dynamic programming and planarity: improved tree-decomposition based algorithms ⋮ \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth ⋮ Total restrained domination in claw-free graphs ⋮ Trees with equal domination and restrained domination numbers ⋮ Restrained domination in cubic graphs ⋮ Boolean-width of graphs ⋮ On the Boolean-Width of a Graph: Structure and Applications ⋮ Restrained bondage in graphs ⋮ A $c^k n$ 5-Approximation Algorithm for Treewidth ⋮ Width, depth, and space: tradeoffs between branching and dynamic programming ⋮ Cluster deletion on interval graphs and split related graphs ⋮ Worm colorings ⋮ Restrained and Total Restrained Domination in Graphs ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width ⋮ Extension problems with degree bounds ⋮ Graph Classes with Structured Neighborhoods and Algorithmic Applications ⋮ Grundy number on -classes ⋮ Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth ⋮ Total restrained domination in cubic graphs ⋮ A survey of stratified domination in graphs ⋮ Computing the chromatic number using graph decompositions via matrix rank ⋮ Mim-width. III. Graph powers and generalized distance domination problems ⋮ More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints ⋮ Restrained condition on double Roman dominating functions ⋮ Edge dominating set and colorings on graphs with fixed clique-width ⋮ Counting \(H-\)colorings of partial \(k-\)trees ⋮ The \(k\)-separator problem: polyhedra, complexity and approximation results
This page was built for publication: Algorithms for Vertex Partitioning Problems on Partial k-Trees
