Finding a Maximum Induced Degenerate Subgraph Faster Than 2 n

DOI10.1007/978-3-642-33293-7_3zbMath1374.68726arXiv1208.4449OpenAlexW2113826940MaRDI QIDQ4899236

Marcin Pilipczuk, Michał Pilipczuk

Publication date: 7 January 2013

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1208.4449

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (9)

Faster exact algorithms for some terminal set problems ⋮ On the number of connected sets in bounded degree graphs ⋮ On Subgraphs of Bounded Degeneracy in Hypergraphs ⋮ Largest chordal and interval subgraphs faster than \(2^n\) ⋮ Solving target set selection with bounded thresholds faster than \(2^n\) ⋮ Solving Target Set Selection with Bounded Thresholds Faster than 2^n ⋮ Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph ⋮ Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity ⋮ Subexponential-time algorithms for finding large induced sparse subgraphs

This page was built for publication: Finding a Maximum Induced Degenerate Subgraph Faster Than 2 n