On enumerating all minimal solutions of feedback problems
From MaRDI portal
Publication:1348395
DOI10.1016/S0166-218X(00)00339-5zbMath1004.68122WikidataQ56881280 ScholiaQ56881280MaRDI QIDQ1348395
Benno Schwikowski, Ewald Speckenmeyer
Publication date: 15 May 2002
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Related Items
Proximity Search for Maximal Subgraph Enumeration ⋮ Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs ⋮ Efficient enumeration of graph orientations with sources ⋮ Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization ⋮ Improved bounds for minimal feedback vertex sets in tournaments ⋮ Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity ⋮ Unique key Horn functions ⋮ Enumeration of irredundant forests ⋮ Polynomial-delay and polynomial-space enumeration of large maximal matchings ⋮ An Exact Method for the Minimum Feedback Arc Set Problem ⋮ Enumerating minimal dominating sets in chordal bipartite graphs ⋮ Unnamed Item ⋮ Invited talks ⋮ Feedback Vertex Sets in Tournaments ⋮ Subset feedback vertex sets in chordal graphs ⋮ Enumerating minimal subset feedback vertex sets ⋮ Generating cut conjunctions in graphs and related problems ⋮ Listing Maximal Subgraphs Satisfying Strongly Accessible Properties ⋮ An incremental polynomial time algorithm to enumerate all minimal edge dominating sets ⋮ On enumerating minimal dicuts and strongly connected subgraphs ⋮ Open problems around exact algorithms ⋮ On the minimum feedback vertex set problem: Exact and enumeration algorithms ⋮ Fixed-parameter tractability results for feedback set problems in tournaments ⋮ Telling stories: enumerating maximal directed acyclic graphs with a constrained set of sources and targets ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Generating 3-vertex connected spanning subgraphs ⋮ Combinatorial algorithms for feedback problems in directed graphs ⋮ On the complexity of solution extension of optimization problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On generating all maximal independent sets
- The maximum clique problem
- On Minimum Cost Recovery from System Deadlock
- Hard Enumeration Problems in Geometry and Combinatorics
- Feedback vertex sets and cyclically reducible graphs
- A Graph Theoretic Approach to Statistical Data Security
- Enumeration of all minimum feedback edge sets in a directed graph
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- A New Algorithm for Generating All the Maximal Independent Sets
- A Minimax Theorem for Directed Graphs
- An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs
- Generating the Acyclic Orientations of a Graph