Genus characterizes the complexity of certain graph problems: Some tight results

DOI10.1016/J.JCSS.2006.11.001MaRDI QIDQ2641866zbMATH OpenOpenAlexFDO

Authors Ljubomir Perković, Eric Sedgwick, Ge Xia, Jianer Chen, Iyad Kanj

Publication date 23 August 2007

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2006.11.001

zbMATH Keywords

graph genusparameterized computationpolynomial time approximation schemesubexponential time computation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 2038759
• A note on approximating graph genus
• The graph genus problem is NP-complete
• Beyond the Euler characteristic: approximating the genus of general graphs (extended abstract)
• On the lower bounds for the maximum genus for simple graphs
• scientific article; zbMATH DE number 495474
• scientific article; zbMATH DE number 1501715
• On the genus of some total graphs
• On the genus and thickness of graphs

Cites work

• A note on approximating graph genus
• A refined search tree technique for dominating set on planar graphs
• Algorithmic graph embeddings
• Applications of a Planar Separator Theorem
• Approximation algorithms for NP-complete problems on planar graphs
• Automata, Languages and Programming
• Efficient bounds for the stable set, vertex cover and set packing problems
• Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
• scientific article; zbMATH DE number 4006288 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305522 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 2038759 (Why is no real title available?)
• scientific article; zbMATH DE number 2079336 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 1929955 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• On the existence of subexponential parameterized algorithms
• Optimization, approximation, and complexity classes
• Parameterized complexity: exponential speed-up for planar graph problems
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Polynomial-time data reduction for dominating set
• Proof verification and the hardness of approximation problems
• Strong computational lower bounds via parameterized complexity
• Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
• The dominating set problem is fixed parameter tractable for graphs of bounded genus
• The graph genus problem is NP-complete
• Tight lower bounds for certain parameterized NP-hard problems
• Vertex cover: Further observations and further improvements
• Vertex packings: Structural properties and algorithms
• Which problems have strongly exponential complexity?

Cited in

(15)

• On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
• A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation
• Revising Johnson's table for the 21st century
• Genus from sandpile torsor algorithm
• The genus of the balanced hypercube
• scientific article; zbMATH DE number 2089221 (Why is no real title available?)
• Computing strong metric dimension of some special classes of graphs by genetic algorithms
• scientific article; zbMATH DE number 2038759 (Why is no real title available?)
• scientific article; zbMATH DE number 4001498 (Why is no real title available?)
• The dominating set problem is fixed parameter tractable for graphs of bounded genus
• Coverability and sub-exponential parameterized algorithms in planar graphs
• Stronger ILPs for the Graph Genus Problem.
• Almost tight lower bounds for hard cutting problems in embedded graphs
• Maximum cut parameterized by crossing number
• Bounds on the genus for 2-cell embeddings of prefix-reversal graphs

This page was built for publication: Genus characterizes the complexity of certain graph problems: Some tight results

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