Node-Deletion Problems on Bipartite Graphs
From MaRDI portal
Publication:3921261
DOI10.1137/0210022zbMath0468.05044OpenAlexW2141925838MaRDI QIDQ3921261
Publication date: 1981
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0210022
Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)
Related Items (only showing first 100 items - show all)
Complexity of learning in concept lattices from positive and negative examples ⋮ Implications of forbidden structures for extremal algorithmic problems ⋮ Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration ⋮ Augmenting approach for some maximum set problems ⋮ Polynomial time recognition of vertices contained in all (or no) maximum dissociation sets of a tree ⋮ A linear-time algorithm for the weighted feedback vertex problem on interval graphs ⋮ Bandwidth of chain graphs ⋮ An efficient polynomial time approximation scheme for the vertex cover \(P_3\) problem on planar graphs ⋮ Circular convex bipartite graphs: feedback vertex sets ⋮ On Halin subgraphs and supergraphs ⋮ Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs ⋮ Maximal and maximum dissociation sets in general and triangle-free graphs ⋮ Optimal edge ranking of trees in polynomial time ⋮ Linear structure of bipartite permutation graphs and the longest path problem ⋮ Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ New upper bounds on feedback vertex numbers in butterflies ⋮ The maximum k-colorable subgraph problem for chordal graphs ⋮ Graph modification problem for some classes of graphs ⋮ On edge perfectness and classes of bipartite graphs ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Recognizing interval digraphs and interval bigraphs in polynomial time ⋮ Matching interdiction ⋮ New Results on Directed Edge Dominating Set ⋮ A probabilistic estimator for the vertex deletion problem ⋮ Minimal dominating sets in graph classes: combinatorial bounds and enumeration ⋮ Solving Matching Problems Efficiently in Bipartite Graphs ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ Feedback vertex sets on restricted bipartite graphs ⋮ Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs ⋮ On the weighted \(k\)-path vertex cover problem ⋮ Minimum \(d\)-blockers and \(d\)-transversals in graphs ⋮ A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs ⋮ The maximum cardinality cut problem in co-bipartite chain graphs ⋮ A faster FPT algorithm for 3-path vertex cover ⋮ Algorithms for induced biclique optimization problems ⋮ Unnamed Item ⋮ On the \(d\)-claw vertex deletion problem ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization ⋮ The chain graph sandwich problem ⋮ A characterization of chain probe graphs ⋮ Two characterizations of chain partitioned probe graphs ⋮ On computing the minimum 3-path vertex cover and dissociation number of graphs ⋮ On the vertex \(k\)-path cover ⋮ Kernelization and Parameterized Algorithms for 3-Path Vertex Cover ⋮ Monotonizing linear programs with up to two nonzeroes per column ⋮ A fixed-parameter algorithm for the vertex cover \(P_3\) problem ⋮ \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems ⋮ On the Hardness of Energy Minimisation for Crystal Structure Prediction ⋮ Some new considerations about double nested graphs ⋮ Two Hardness Results on Feedback Vertex Sets ⋮ ACYCLIC MATCHINGS IN SUBCLASSES OF BIPARTITE GRAPHS ⋮ Approximate association via dissociation ⋮ 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 ⋮ The critical node detection problem in networks: a survey ⋮ The geodesic-transversal problem ⋮ Stable-\(\Pi\) partitions of graphs ⋮ Edge deletion problems: branching facilitated by modular decomposition ⋮ Improved approximation algorithms for path vertex covers in regular graphs ⋮ Minimum \(k\)-path vertex cover ⋮ The complexity of dissociation set problems in graphs ⋮ An efficient algorithm for minimum feedback vertex sets in rotator graphs ⋮ Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs ⋮ On the complete width and edge clique cover problems ⋮ Vertex deletion problems on chordal graphs ⋮ The induced matching and chain subgraph cover problems for convex bipartite graphs ⋮ ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES ⋮ Secure total domination in chain graphs and cographs ⋮ Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions ⋮ Approximation Algorithms for Minimum Chain Vertex Deletion ⋮ Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results ⋮ On sum coloring of graphs ⋮ Minimum fill-in: inapproximability and almost tight lower bounds ⋮ Subset feedback vertex set on graphs of bounded independent set size ⋮ On the complexity of the k-chain subgraph cover problem ⋮ Some results on graphs without long induced paths ⋮ Partitioning a graph into small pieces with applications to path transversal ⋮ Incompressibility of \(H\)-free edge modification problems: towards a dichotomy ⋮ A polynomial kernel for diamond-free editing ⋮ The lexicographically first maximal subgraph problems:P-completeness andNC algorithms ⋮ A good submatrix is hard to find ⋮ Relating dissociation, independence, and matchings ⋮ Blockers and transversals ⋮ THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS ⋮ The \(k\)-path vertex cover in Cartesian product graphs and complete bipartite graphs ⋮ Edge-contraction problems ⋮ Conjunctive-query containment and constraint satisfaction ⋮ Connected matchings in chordal bipartite graphs ⋮ Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs ⋮ Independent packings in structured graphs ⋮ Circular Convex Bipartite Graphs: Feedback Vertex Set ⋮ The \(k\)-path vertex cover of rooted product graphs ⋮ Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT ⋮ The \(k\)-separator problem: polyhedra, complexity and approximation results ⋮ Extracting embedded generalized networks from linear programming problems ⋮ Computing the Minimum Fill-In is NP-Complete
This page was built for publication: Node-Deletion Problems on Bipartite Graphs
