On the complexity of solution extension of optimization problems
From MaRDI portal
Publication:2072063
DOI10.1016/j.tcs.2021.10.017OpenAlexW3209430198MaRDI QIDQ2072063
Mehdi Khosravian Ghadikolaei, Florian Sikora, Henning Fernau, Jérôme Monnot, Katrin Casel
Publication date: 1 February 2022
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1810.04553
Related Items
In memory of Jérôme Monnot ⋮ Minimal Roman dominating functions: extensions and enumeration ⋮ Extension of some edge graph problems: standard, parameterized and approximation complexity ⋮ Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes ⋮ Extension and its price for the connected vertex cover problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimal dominating sets in interval graphs and trees
- Fundamentals of parameterized complexity
- An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- On product covering in 3-tier supply chain models: natural complete problems for W[3 and W[4]]
- Enumerating minimal dominating sets in chordal bipartite graphs
- A special planar satisfiability problem and a consequence of its NP- completeness
- On enumerating all minimal solutions of feedback problems
- Theoretical computer science. Introduction to automata, computability, complexity, algorithmics, randomization, communication, and cryptography.
- Which problems have strongly exponential complexity?
- The many facets of upper domination
- Synchronizing words and monoid factorization: a parameterized perspective
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- Extension of some edge graph problems: standard and parameterized complexity
- Extension of Vertex Cover and Independent Set in some classes of graphs
- Extension and its price for the Connected Vertex Cover problem
- On enumerating minimal dicuts and strongly connected subgraphs
- Dual-Bounded Generating Problems: Partial and Multiple Transversals of a Hypergraph
- A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs
- Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs
- On feedback vertex sets and nonseparating independent sets in cubic graphs
- Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
- A Minimax Theorem for Directed Graphs
- Dual subimplicants of positive Boolean functions
- Reducibility among Combinatorial Problems
- Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling
- Computational Complexity
- On the Complexity of Some Enumeration Problems for Matroids
- Parameterized Algorithms
- On cliques in graphs
