Graph classes with structured neighborhoods and algorithmic applications

DOI10.1016/j.tcs.2013.01.011zbMath1408.68109OpenAlexW1964095725MaRDI 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 decompositiongraph classesBoolean widthvertex partitioning problems

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) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (41)

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

This page was built for publication: Graph classes with structured neighborhoods and algorithmic applications