Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT
From MaRDI portal
Publication:2632009
DOI10.1016/j.tcs.2018.11.009zbMath1421.68088arXiv1809.01998OpenAlexW2891710764WikidataQ128930596 ScholiaQ128930596MaRDI QIDQ2632009
Publication date: 17 May 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1809.01998
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear-time algorithm for the weighted feedback vertex problem on interval graphs
- Heuristics for deciding collectively rational consumption behavior
- Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete
- Testing flow graph reducibility
- Node listings for reducible flow graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Approximating minimum feedback sets and multicuts in directed graphs
- Packing directed circuits fractionally
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- Coloring Graphs Using Two Colors While Avoiding Monochromatic Cycles
- Feedback vertex sets and cyclically reducible graphs
- A contraction algorithm for finding small cycle cutsets
- Interval digraphs: An analogue of interval graphs
- A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs
- Robust linear algorithms for cutsets
- Characterizations of Reducible Flow Graphs
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- Feedback vertex set on cocomparability graphs
- Reducibility among Combinatorial Problems
- The complexity of satisfiability problems
