Complexity classification of some edge modification problems
From MaRDI portal
Publication:5948964
DOI10.1016/S0166-218X(00)00391-7zbMath0982.68104WikidataQ127647158 ScholiaQ127647158MaRDI QIDQ5948964
Ron Shamir, Assaf Natanzon, Roded Sharan
Publication date: 16 January 2002
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Minimal triangulations of graphs: a survey, A vertex incremental approach for maintaining chordality, On the effectiveness of the incremental approach to minimal chordal edge modification, Orthology Relation and Gene Tree Correction: Complexity Results, Additive approximation of generalized Turán questions, Cluster graph modification problems, Win-win kernelization for degree sequence completion problems, Chordal editing is fixed-parameter tractable, Editing Graphs Into Few Cliques: Complexity, Approximation, and Kernelization Schemes, Deleting edges to restrict the size of an epidemic: a new application for treewidth, Prim-based support-graph preconditioners for min-cost flow problems, Additive approximation for edge-deletion problems, Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth, Graph editing to a fixed target, Editing to a Planar Graph of Given Degrees, Graph modification problem for some classes of graphs, Two edge modification problems without polynomial kernels, Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone, Complexity of modification problems for best match graphs, Matching interdiction, Polynomial kernels for 3-leaf power graph modification problems, Editing to a connected graph of given degrees, On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}, Completion to chordal distance-hereditary graphs: a quartic vertex-kernel, On the computational complexity of the bipartizing matching problem, Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem, Wheel-Free Deletion Is W[2-Hard], Splitting plane graphs to outerplanarity, Editing to Eulerian graphs, Characterizing and Computing Minimal Cograph Completions, A survey of parameterized algorithms and the complexity of edge modification, On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints, Unnamed Item, Parameterized complexity of even/odd subgraph problems, On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems, Cograph editing: Merging modules is equivalent to editing P_4s, Contracting graphs to paths and trees, Parameterized complexity of Eulerian deletion problems, A cubic-vertex kernel for flip consensus tree, Strongly chordal and chordal bipartite graphs are sandwich monotone, Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs, Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs, Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes, Minimal comparability completions of arbitrary graphs, Complexity and parameterized algorithms for cograph editing, Minimal split completions, On the complexity of some subgraph problems, Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs, Characterizing and computing minimal cograph completions, Chordal deletion is fixed-parameter tractable, On listing, sampling, and counting the chordal graphs with edge constraints, Applying modular decomposition to parameterized cluster editing problems, NP-completeness results for edge modification problems, Contracting chordal graphs and bipartite graphs to paths and trees, Efficient Algorithms for Eulerian Extension, On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems, Editing to a planar graph of given degrees, Subexponential parameterized algorithms and kernelization on almost chordal graphs, Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions, A new approximate cluster deletion algorithm for diamond-free graphs, Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results, On the threshold of intractability, Contracting chordal graphs and bipartite graphs to paths and trees, Dynamically maintaining split graphs, Unnamed Item, Incompressibility of \(H\)-free edge modification problems: towards a dichotomy, Parameterized Complexity of Eulerian Deletion Problems, Hardness of edge-modification problems, Two Edge Modification Problems without Polynomial Kernels, Blockers and transversals, Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid, THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS, (Sub)linear kernels for edge modification problems toward structured graph classes, Modifying a graph using vertex elimination, Faster parameterized algorithms for deletion to split graphs, Covering tree with stars, Editing to a graph of given degrees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Orienting graphs to optimize reachability
- The node-deletion problem for hereditary properties is NP-complete
- The splittance of a graph
- Some simplified NP-complete graph problems
- Bounded degree interval sandwich problems
- Some complexity results about threshold graphs
- On the complexity of DNA physical mapping
- Fixed-parameter tractability of graph modification problems for hereditary properties
- A characterization of perfect graphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- An Application of Duality to Edge-Deletion Problems
- The complexity of some edge deletion problems
- Edge-Deletion Problems
- Computing the Minimum Fill-In is NP-Complete
- Graph Classes: A Survey
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Complexity and algorithms for reasoning about time
- Asteroidal Triple-Free Graphs
- Gadgets, Approximation, and Linear Programming
- A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
- The approximation of maximum subgraph problems
- Graph Sandwich Problems
- Threshold Numbers and Threshold Completions
- On intervalizing \(k\)-colored graphs for DNA physical mapping
