Graph classes with structured neighborhoods and algorithmic applications
From MaRDI portal
Recommendations
- Graph classes with structured neighborhoods and algorithmic applications
- scientific article; zbMATH DE number 6470121
- scientific article; zbMATH DE number 4027496
- Graph Classes: A Survey
- scientific article; zbMATH DE number 4093511
- scientific article; zbMATH DE number 4103126
- Neighborhood classes of H-comparability graphs
- scientific article; zbMATH DE number 3849278
- scientific article; zbMATH DE number 409491
- Constructing and classifying neighborhood anti-Sperner graphs
Cites work
- A linear time algorithm to recognize circular permutation graphs
- 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
- Approximating clique-width and branch-width
- Boolean-width of graphs
- Branch-width and well-quasi-ordering in matroids and graphs.
- Clustering and domination in perfect graphs
- Computing role assignments of chordal graphs
- Decomposition of perfect graphs
- Domination in convex and chordal bipartite graphs
- Domination in permutation graphs
- Dominations in trapezoid graphs
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- Fast algorithms for the dominating set problem on permutation graphs
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Graph minors. X: Obstructions to tree-decomposition
- scientific article; zbMATH DE number 3919840 (Why is no real title available?)
- scientific article; zbMATH DE number 1983292 (Why is no real title available?)
- scientific article; zbMATH DE number 2079335 (Why is no real title available?)
- scientific article; zbMATH DE number 794265 (Why is no real title available?)
- Independence and domination in polygon graphs
- Linear time algorithms on circular-arc graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Linear-time recognition of circular-arc graphs
- Measuring the vulnerability for classes of intersection graphs
- Node-Deletion Problems on Bipartite Graphs
- On the 2-Chain Subgraph Cover and Related Problems
- Polygon Graph Recognition
- Recognition algorithms for orders of small width and graphs of small Dilworth number
- Some simplified NP-complete graph problems
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The complexity of domination problems in circle graphs
- The Complexity of the Partial Order Dimension Problem
- The Hardness of Approximating Poset Dimension
- The Rank-Width of the Square Grid
- Treewidth and Minimum Fill-in on d-Trapezoid Graphs
- Weighted domination of cocomparability graphs
Cited in
(59)- 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₁,H₂)-free graphs
- Scattered packings of cycles
- Graph classes with structured neighborhoods and algorithmic applications
- scientific article; zbMATH DE number 4193150 (Why is no real title available?)
- A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
- scientific article; zbMATH DE number 3849278 (Why is no real title available?)
- Distance domination in graphs
- scientific article; zbMATH DE number 4027496 (Why is no real title available?)
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
- Generalized distance domination problems and their complexity on graphs of bounded mim-width
- On the tractability of optimization problems on \(H\)-graphs
- More applications of the d-neighbor equivalence: connectivity and acyclicity constraints
- Neighborhood complexity and kernelization for nowhere dense classes of graphs
- Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
- scientific article; zbMATH DE number 6470121 (Why is no real title available?)
- 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.
- Treewidth versus clique number. II: Tree-independence number
- Solving problems on generalized convex graphs via mim-width
- Classes of intersection digraphs with good algorithmic properties
- On \(d\)-stable locally checkable problems parameterized by mim-width
- Classifying subset feedback vertex set for \(H\)-free graphs
- List 3-coloring on comb-convex and caterpillar-convex bipartite graphs
- Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
- Approximation hardness of domination problems on generalized convex graphs
- Parameterized algorithms for locating-dominating sets
- Isometric path complexity of graphs
- Finding induced subgraphs from graphs with small mim-width
- The simultaneous interval number: a new width parameter that measures the similarity to interval graphs
- On the hardness of generalized domination problems parameterized by mim-width
- Comparing width parameters on graph classes
- Computing subset vertex covers in H-free graphs
- Hamiltonicity parameterized by mim-width is (indeed) para-NP-hard
- Connected partitions via connected dominating sets
- On algorithmic applications of \(\mathcal{F}\)-branchwidth
- Mim-width is paraNP-complete
- Solving problems on generalized convex graphs via mim-width
This page was built for publication: Graph classes with structured neighborhoods and algorithmic applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q392023)
