Lower bounds for protrusion replacement by counting equivalence classes

DOI10.1016/J.DAM.2019.02.024zbMATH Open1437.05224OpenAlexW2963511265WikidataQ128267947 ScholiaQ128267947MaRDI QIDQ2174552FDOQ2174552

Authors: Bart M. P. Jansen, Jules Wulms 

Publication date: 21 April 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/6927/

Recommendations

• Lower bounds for protrusion replacement by counting equivalence classes
• Lower bounds and the hardness of counting properties
• Lower bounds for the class number
• Number of bounded distance equivalence classes in hulls of repetitive Delone sets
• A lower bound for congruence representations
• Uniform lower bound for intersection numbers of \(\psi\)-classes
• Complexity classes of equivalence problems revisited
• Characterizations and approximability of hard counting classes below \#\textsf{P}
• On the succinct representation of equivalence classes

zbMATH Keywords

independent setequivalence classesfinite integer indexboundaried graphsprotrusions

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Dynamic programming (90C39) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• Parameterized algorithms
• Some simplified NP-complete graph problems
• Kernelization using structural parameters on sparse graph classes
• Hitting forbidden minors: approximation and kernelization
• Title not available (Why is that?)
• Title not available (Why is that?)
• Planar graphs, via well-orderly maps and trees
• Mixed searching and proper-path-width
• Reduction algorithms for graphs of small treewidth
• Explicit linear kernels via dynamic programming
• Vertex cover structural parameterization revisited
• (Meta) kernelization
• The effect of planarization on width
• The effect of planarization on width

Cited In (3)

• The effect of planarization on width
• Lower bounds for protrusion replacement by counting equivalence classes
• Lower bounds for dynamic programming on planar graphs of bounded cutwidth

This page was built for publication: Lower bounds for protrusion replacement by counting equivalence classes

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