Graph classes with structured neighborhoods and algorithmic applications

DOI10.1016/j.tcs.2013.01.011zbMath1408.68109MaRDI QIDQ392023

Rémy Belmonte, Martin Vatshelle

Publication date: 13 January 2014

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

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

zbMATH Keywords

graph decomposition; graph classes; Boolean width; vertex partitioning problems

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C75: Structural characterization of families of graphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints, Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs, The perfect matching cut problem revisited, The perfect matching cut problem revisited, Node multiway cut and subset feedback vertex set on graphs of bounded mim-width, Classifying subset feedback vertex set for \(H\)-free graphs, Bounding the mim‐width of hereditary graph classes, Clique‐width: Harnessing the power of atoms, Bounding the Mim-Width of Hereditary Graph Classes., Scattered packings of cycles, Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems, Solving problems on generalized convex graphs via mim-width, A width parameter useful for chordal and co-comparability graphs, Output-polynomial enumeration on graphs of bounded (local) linear MIM-width, Maximum rooted connected expansion, Measuring what matters: a hybrid approach to dynamic programming with treewidth, Revising Johnson's table for the 21st century, A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs, Star colouring of bounded degree graphs and regular graphs, Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage, Mim-width. I. Induced path problems, On the tractability of optimization problems on \(H\)-graphs, List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective, On pairwise compatibility graphs having Dilworth number \(k\), Mim-width. II. The feedback vertex set problem, Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width, New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs, Mim-width. III. Graph powers and generalized distance domination problems, Lower bounds on the mim-width of some graph classes, Faster algorithms for vertex partitioning problems parameterized by clique-width, On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs, Unnamed Item, Distance Domination in Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Independence and domination in polygon graphs
• Computing role assignments of chordal graphs
• Boolean-width of graphs
• Domination in convex and chordal bipartite graphs
• Clustering and domination in perfect graphs
• Decomposition of perfect graphs
• Graph minors. X: Obstructions to tree-decomposition
• Linear time algorithms on circular-arc graphs
• The complexity of domination problems in circle graphs
• Some simplified NP-complete graph problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Dominations in trapezoid graphs
• Measuring the vulnerability for classes of intersection graphs
• Weighted domination of cocomparability graphs
• Linear-time recognition of circular-arc graphs
• Recognition algorithms for orders of small width and graphs of small Dilworth number
• Branch-width and well-quasi-ordering in matroids and graphs.
• Linear time solvable optimization problems on graphs of bounded clique-width
• Fast algorithms for the dominating set problem on permutation graphs
• Approximating clique-width and branch-width
• The Hardness of Approximating Poset Dimension
• The Complexity of the Partial Order Dimension Problem
• Domination in permutation graphs
• Node-Deletion Problems on Bipartite Graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• On the 2-Chain Subgraph Cover and Related Problems
• Polygon Graph Recognition
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• An $O(N + M)$-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph
• A linear time algorithm to recognize circular permutation graphs
• The Rank-Width of the Square Grid