Output-polynomial enumeration on graphs of bounded (local) linear MIM-width

DOI10.1007/s00453-017-0289-1zbMath1383.05162arXiv1509.03753OpenAlexW1922215400MaRDI QIDQ1709594

Petr A. Golovach, Pinar Heggernes, Yngve Villanger, Mamadou Moustapha Kanté, Dieter Kratsch, Sigve Hortemo Sæther

Publication date: 6 April 2018

Published in: Algorithmica, Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1509.03753

zbMATH Keywords

linear delaydomination problemlocal linear MIM-widthoutput-polynomial enumerationlinear maximum induced matching width of a graphLMIM-width

Mathematics Subject Classification ID

Graph polynomials (05C31) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Proximity Search for Maximal Subgraph Enumeration, Counting Minimal Dominating Sets, Enumerating Minimal Transversals of Hypergraphs without Small Holes, Locally definable vertex set properties are efficiently enumerable, Enumerating models of DNF faster: breaking the dependency on the formula size, Efficient enumeration of dominating sets for sparse graphs, Unnamed Item, Unnamed Item, On the dualization in distributive lattices and related problems, Enumerating Minimal Dominating Sets in Triangle-Free Graphs, 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

Cites Work

• Unnamed Item
• Graph classes with structured neighborhoods and algorithmic applications
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
• Enumerating minimal dominating sets in chordal bipartite graphs
• Linear delay enumeration and monadic second-order logic
• On the cubicity of interval graphs
• On generating all maximal independent sets
• Reverse search for enumeration
• On enumerating minimal dicuts and strongly connected subgraphs
• A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs
• On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs
• The Bidimensional Theory of Bounded-Genus Graphs
• Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Graph Classes: A Survey
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• On the Neighbourhood Helly of Some Graph Classes and Applications to the Enumeration of Minimal Dominating Sets
• Enumeration of the Elementary Circuits of a Directed Graph
• On the Enumeration of Minimal Dominating Sets and Related Notions
• Bidimensional Parameters and Local Treewidth
• Generating all vertices of a polyhedron is hard