Some APX-completeness results for cubic graphs
From MaRDI portal
Publication:1566710
DOI10.1016/S0304-3975(98)00158-3zbMath0939.68052OpenAlexW2012391569WikidataQ56032472 ScholiaQ56032472MaRDI QIDQ1566710
Publication date: 4 June 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(98)00158-3
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (only showing first 100 items - show all)
Disjointness graphs of segments in the space ⋮ Semipaired Domination in Some Subclasses of Chordal Graphs ⋮ Acyclic Matching in Some Subclasses of Graphs ⋮ Complexity Insights of the Minimum Duplication Problem ⋮ Improved algorithms for some competitive location centroid problems on paths, trees and graphs ⋮ Complexity results for rainbow matchings ⋮ Algorithmic Aspects of Disjunctive Domination in Graphs ⋮ On Finding Small 2-Generating Sets ⋮ Aligning and Labeling Genomes under the Duplication-Loss Model ⋮ Angle Covers: Algorithms and Complexity ⋮ New Results on Directed Edge Dominating Set ⋮ The Parameterized Complexity of the Rainbow Subgraph Problem ⋮ On the tractability of finding disjoint clubs in a network ⋮ Complexity of (arc)-connectivity problems involving arc-reversals or deorientations ⋮ Acyclic matching in some subclasses of graphs ⋮ Algorithmic aspects of paired disjunctive domination in graphs ⋮ Exact algorithms and hardness results for geometric red-blue hitting set problem ⋮ Complexity results on cosecure domination in graphs ⋮ Complexity and Approximation Results for the Connected Vertex Cover Problem ⋮ On the partial vertex cover problem in bipartite graphs -- a parameterized perspective ⋮ Algorithmic results on locating-total domination in graphs ⋮ Algorithmic results in Roman dominating functions on graphs ⋮ Unnamed Item ⋮ Untangling temporal graphs of bounded degree ⋮ Computing maximum matchings in temporal graphs ⋮ The complexity of spanning tree problems involving graphical indices ⋮ Finding Points in General Position ⋮ Hardness and approximation results of Roman \{3\}-domination in graphs ⋮ On defensive alliances and strong global offensive alliances ⋮ A note on vertices contained in the minimum dominating set of a graph with minimum degree three ⋮ Secure connected domination and secure total domination in unit disk graphs and rectangle graphs ⋮ Complexity insights of the minimum duplication problem ⋮ Gene tree correction for reconciliation and species tree inference: complexity and algorithms ⋮ Technical Note—Assortment Optimization with Small Consideration Sets ⋮ Flip distance between triangulations of a planar point set is APX-hard ⋮ Unnamed Item ⋮ On Complexity of Total Vertex Cover on Subcubic Graphs ⋮ Greedy Approximation for Source Location Problem with Vertex-Connectivity Requirements in Undirected Graphs ⋮ COLORING ALGORITHMS ON SUBCUBIC GRAPHS ⋮ Hardness results of global Roman domination in graphs ⋮ The source location problem with local 3-vertex-connectivity requirements ⋮ On the Approximability of Comparing Genomes with Duplicates ⋮ NP-hard graph problems and boundary classes of graphs ⋮ Finding Approximate and Constrained Motifs in Graphs ⋮ On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs ⋮ Algorithmic aspects of total Roman ${2}$-domination in graphs ⋮ On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs ⋮ Minimization of decision trees is hard to approximate ⋮ Approximability of the independent feedback vertex set problem for bipartite graphs ⋮ Complexity results on restricted instances of a paint shop problem for words ⋮ Minimum monopoly in regular and tree graphs ⋮ Parameter testing in bounded degree graphs of subexponential growth ⋮ Sports tournaments, home-away assignments, and the break minimization problem ⋮ Graph orientation with splits ⋮ On the Complexity Landscape of the Domination Chain ⋮ b-Disjunctive Total Domination in Graphs: Algorithm and Hardness Results ⋮ Fingerprint clustering with bounded number of missing values ⋮ Domination in Geometric Intersection Graphs ⋮ Approximating the discrete time-cost tradeoff problem with bounded depth ⋮ APX-hardness and approximation for the \(k\)-burning number problem ⋮ APX-hardness and approximation for the \(k\)-burning number problem ⋮ Approximating the discrete time-cost tradeoff problem with bounded depth ⋮ Weighted Upper Edge Cover: Complexity and Approximability ⋮ A Dynamic Programming Approach for a Class of Robust Optimization Problems ⋮ On the Complexity of Approximation and Online Scheduling Problems with Applications to Optical Networks ⋮ Revisiting connected vertex cover: FPT algorithms and lossy kernels ⋮ Comparing incomplete sequences via longest common subsequence ⋮ The complexity of solution-free sets of integers for general linear equations ⋮ Algorithm and hardness results on hop domination in graphs ⋮ Computational complexity of minimum \(P_4\) vertex cover problem for regular and \(K_{1, 4}\)-free graphs ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure ⋮ Unnamed Item ⋮ Algorithmic complexity of weakly connected Roman domination in graphs ⋮ Stackelberg Max Closure with Multiple Followers ⋮ Algorithmic aspects of total Roman {3}-domination in graphs ⋮ On the complexity of the vector connectivity problem ⋮ Approximability and hardness of geometric hitting set with axis-parallel rectangles ⋮ Algorithmic aspects of total Roman and total double Roman domination in graphs ⋮ A natural family of optimization problems with arbitrarily small approximation thresholds ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ Algorithmic results in secure total dominating sets on graphs ⋮ Subset sum problems with digraph constraints ⋮ Approximability and exact resolution of the multidimensional binary vector assignment problem ⋮ Finding disjoint paths on edge-colored graphs: more tractability results ⋮ On the complexity of and solutions to the minimum stopping and trapping set problems ⋮ The label cut problem with respect to path length and label frequency ⋮ Complexity issues in color-preserving graph embeddings ⋮ On the longest common rigid subsequence problem ⋮ Approximation algorithm and hardness results for defensive domination in graphs ⋮ Finding a collective set of items: from proportional multirepresentation to group recommendation ⋮ Complexity of \(k\)-tuple total and total \(\{k\}\)-dominations for some subclasses of bipartite graphs ⋮ Algorithmic aspects of open neighborhood location-domination in graphs ⋮ Robust combinatorial optimization with locally budgeted uncertainty ⋮ Parameterized complexity of \(k\)-anonymity: hardness and tractability ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ Exact algorithms and APX-hardness results for geometric packing and covering problems ⋮ Finding approximate and constrained motifs in graphs ⋮ A novel parameterised approximation algorithm for \textsc{minimum vertex cover} ⋮ The \(l\)-diversity problem: tractability and approximability ⋮ On the complexity of computing MP distance between binary phylogenetic trees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximating the minimum maximal independence number
- Completeness in approximation classes
- Maximum bounded 3-dimensional matching is MAX SNP-complete
- Optimization, approximation, and complexity classes
- On approximation properties of the independent set problem for low degree graphs
- The complexity and approximability of finding maximum feasible subsystems of linear relations
- Structure in Approximation Classes
- On the hardness of approximating minimization problems
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
This page was built for publication: Some APX-completeness results for cubic graphs
