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
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, Approximating Bounded Degree Deletion via Matroid Matching, Unnamed Item, A \(5k\)-vertex kernel for 3-path vertex cover, A bound on the dissociation number, The maximum number of maximum dissociation sets in trees, Linear‐time algorithms for eliminating claws in graphs, The k‐path vertex cover: General bounds and chordal graphs, Certifying induced subgraphs in large graphs, Relating the independence number and the dissociation number, Domination number and feedback vertex number of complements of line graphs, Deletion to scattered graph classes. I: Case of finite number of graph classes, Maximum weight t-sparse set problem on vector-weighted graphs, Treewidth versus clique number. II: Tree-independence number, Unnamed Item, Maximum dissociation sets in subcubic trees, On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number, On the Harary Index of Graphs with Given Dissociation Number, Extremal vertex-degree function index with given order and dissociation number, On spectral extrema of graphs with given order and dissociation number, Minimum number of maximal dissociation sets in trees, On the maximum number of maximum dissociation sets in trees with given dissociation number, Unnamed Item, Chordless Cycle Packing Is Fixed-Parameter Tractable, Between 2- and 3-colorability, Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage, Biclique graphs and biclique matrices, Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs, On the \(d\)-claw vertex deletion problem, Graph square roots of small distance from degree one graphs, Parameterized algorithms for finding highly connected solution, Vertex deletion on split graphs: beyond 4-hitting set, Approximating Partially Bounded Degree Deletion on Directed Graphs, General d-position sets, Parameterized algorithms for finding highly connected solution, On the Hardness of Energy Minimisation for Crystal Structure Prediction*, 3-path vertex cover and dissociation number of hexagonal graphs, Vertex Deletion Problems on Chordal Graphs
