Enumerating minimal solution sets for metric graph problems
From MaRDI portal
algorithmic enumerationgeodetic setshypergraph dualizationmatroidsmetric dimensionresolving setsstrong metric dimension
Enumeration in graph theory (05C30) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Metric embeddings as related to computational problems and algorithms (68R12)
Cites work
- A global parallel algorithm for enumerating minimal transversals of geometric hypergraphs
- A Linear Recognition Algorithm for Cographs
- A New Algorithm for Generating All the Maximal Independent Sets
- A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs
- Adaptive identification in graphs
- Algorithms for dualization over products of partially ordered sets
- Algorithms – ESA 2004
- Ample completions of oriented matroids and complexes of uniform oriented matroids
- Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
- Complexity of metric dimension on planar graphs
- Computational aspects of monotone dualization: a brief survey
- Computing minimum geodetic sets of proper interval graphs
- COMs: complexes of oriented matroids
- Discovery of the D-basis in binary tables based on hypergraph dualization
- Domination and location in acyclic graphs
- Dual subimplicants of positive Boolean functions
- Dualization in lattices given by implicational bases
- Efficient enumeration of solutions produced by closure operations
- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- Enumerating disjunctions and conjunctions of paths and cuts in reliability theory
- Enumerating minimal dominating sets in \(K_t\)-free graphs and variants
- Enumerating minimal solution sets for metric graph problems
- Enumerating minimal transversals of hypergraphs without small holes
- Enumeration complexity
- Exploring the gap between treedepth and vertex cover through vertex integrity
- Geometric amortization of enumeration algorithms
- Graph structure and monadic second-order logic. A language-theoretic approach
- Hardness and approximation for the geodetic set problem in some graph classes
- Hardness of metric dimension in graphs of constant treewidth
- scientific article; zbMATH DE number 4031953 (Why is no real title available?)
- scientific article; zbMATH DE number 3494441 (Why is no real title available?)
- scientific article; zbMATH DE number 3544092 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 7650296 (Why is no real title available?)
- scientific article; zbMATH DE number 7765365 (Why is no real title available?)
- Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
- Identifying the Minimal Transversals of a Hypergraph and Related Problems
- Known algorithms for edge clique cover are probably optimal
- Lattice theory.
- Linear delay enumeration and monadic second-order logic
- Listing induced Steiner subgraphs as a compact way to discover Steiner trees in graphs
- Low-dimensional representation of genomic sequences
- Maximal irredundant set enumeration in bounded-degeneracy and bounded-degree hypergraphs
- Metric Dimension of Bounded Tree-length Graphs
- Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
- Metric dimension parameterized by max leaf number
- Metric dimension parameterized by treewidth
- Metric Dimension Parameterized by Treewidth in Chordal Graphs
- New Results on Monotone Dualization and Generating Hypergraph Transversals
- On a new class of codes for identifying vertices in graphs
- On Dualization over Distributive Lattices
- On generating all maximal independent sets
- On Metric Generators of Graphs
- On optimal approximability results for computing the strong metric dimension
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- On the complexity of solution extension of optimization problems
- On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs
- On the enumeration of minimal dominating sets and related notions
- On the parameterized complexity of biclique cover and partition
- Output-polynomial enumeration on graphs of bounded (local) linear MIM-width
- Parameterized complexity of geodetic set
- Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs
- Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs
- Sample Compression Schemes for Balls in Graphs
- Sequential metric dimension
- Strong resolving graphs: the realization and the characterization problems
- Structure-activity maps for visualizing the graph variables arising in drug design
- The (weighted) metric dimension of graphs: hard and easy cases
- The geodetic number of a graph
- The joy of implications, aka pure Horn formulas: mainly a survey
- The strong metric dimension of graphs and digraphs
- The virtual Haken conjecture (with an appendix by Ian Agol, Daniel Groves and Jason Manning).
- Translating between the representations of a ranked convex geometry
- Unlabeled sample compression schemes and corner peelings for ample and maximum classes
- Upper bounds to the clique width of graphs
- Well-partitioned chordal graphs
Cited in
(1)
This page was built for publication: Enumerating minimal solution sets for metric graph problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6980433)
