Node-Deletion Problems on Bipartite Graphs

Cited in

(only showing first 100 items - show all)

Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
Some results on graphs without long induced paths
Blockers and transversals
Implications of forbidden structures for extremal algorithmic problems
The maximum k-colorable subgraph problem for chordal graphs
A probabilistic estimator for the vertex deletion problem
\(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems
On the complexity of the k-chain subgraph cover problem
On Halin subgraphs and supergraphs
Recognizing interval digraphs and interval bigraphs in polynomial time
Monotonizing linear programs with up to two nonzeroes per column
Conjunctive-query containment and constraint satisfaction
An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs
The maximum cardinality cut problem in co-bipartite chain graphs
PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
The critical node detection problem in networks: a survey
Vertex deletion problems on chordal graphs
On sum coloring of graphs
A good submatrix is hard to find
Complexity of learning in concept lattices from positive and negative examples
Optimal edge ranking of trees in polynomial time
On edge perfectness and classes of bipartite graphs
Algorithms for induced biclique optimization problems
Improved approximation algorithms for path vertex covers in regular graphs
Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
A polynomial kernel for diamond-free editing
Relating dissociation, independence, and matchings
Tractability beyond -acyclicity for conjunctive queries with negation and SAT
Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree
Maximal and maximum dissociation sets in general and triangle-free graphs
Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs
The geodesic-transversal problem
Stable-\(\Pi\) partitions of graphs
Edge deletion problems: branching facilitated by modular decomposition
Minimum \(k\)-path vertex cover
The complexity of dissociation set problems in graphs
Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results
Minimum fill-in: inapproximability and almost tight lower bounds
Subset feedback vertex set on graphs of bounded independent set size
Partitioning a graph into small pieces with applications to path transversal
The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs
Connected matchings in chordal bipartite graphs
Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs
The \(k\)-path vertex cover of rooted product graphs
The k-separator problem: polyhedra, complexity and approximation results
Linear structure of bipartite permutation graphs and the longest path problem
New upper bounds on feedback vertex numbers in butterflies
Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
On the vertex \(k\)-path cover
Independent packings in structured graphs
On the d-claw vertex deletion problem
Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs
Augmenting approach for some maximum set problems
Circular convex bipartite graphs: feedback vertex set
A linear-time algorithm for the weighted feedback vertex problem on interval graphs
Minimal dominating sets in graph classes: combinatorial bounds and enumeration
Bandwidth of chain graphs
Solving matching problems efficiently in bipartite graphs
Kernelization and Parameterized Algorithms for 3-Path Vertex Cover
Circular convex bipartite graphs: feedback vertex sets
Two Hardness Results on Feedback Vertex Sets
On computing longest paths in small graph classes
Approximation algorithms for minimum chain vertex deletion
Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
On the hardness of energy minimisation for crystal structure prediction
THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS
Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs
Graph modification problem for some classes of graphs
Extracting embedded generalized networks from linear programming problems
Minimal dominating sets in graph classes: combinatorial bounds and enumeration
Graph classes with structured neighborhoods and algorithmic applications
Feedback vertex sets on restricted bipartite graphs
Computing the Minimum Fill-In is NP-Complete
On the weighted \(k\)-path vertex cover problem
Minimum \(d\)-blockers and \(d\)-transversals in graphs
Algorithms for finding an independent \(\{K_1,K_2\}\)-packing of maximum weight in a graph
Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs with special blocks
The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
A fixed-parameter algorithm for the vertex cover P₃ problem
Acyclic matchings in subclasses of bipartite graphs
Some new considerations about double nested graphs
Secure total domination in chain graphs and cographs
New results on directed edge dominating set
Subset feedback vertex set on graphs of bounded independent set size
General d-position sets
Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
Vertex deletion problems on chordal graphs
Biclique graphs and biclique matrices
The weighted k-path vertex cover problem on series-parallel graphs
Approximating partially bounded degree deletion on directed graphs
Approximating bounded degree deletion via matroid matching
On the hardness of energy minimisation for crystal structure prediction
3-path vertex cover and dissociation number of hexagonal graphs
Chordless Cycle Packing Is Fixed-Parameter Tractable
Incompressibility of H-free edge modification problems: towards a dichotomy
Between 2- and 3-colorability
Parameterized algorithms for finding highly connected solution

This page was built for publication: Node-Deletion Problems on Bipartite Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3921261)