Pathwidth of cubic graphs and exact algorithms
From MaRDI portal
Publication:1045933
DOI10.1016/j.ipl.2005.10.012zbMath1191.68826OpenAlexW2170702810WikidataQ56032469 ScholiaQ56032469MaRDI QIDQ1045933
Publication date: 18 December 2009
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2005.10.012
treewidthcubic graphgraph algorithmspathwidthmaximum independent setexact exponential algorithmmax-cutminimum dominating set
Related Items (31)
Counting Maximal Independent Sets in Subcubic Graphs ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Improved edge-coloring with three colors ⋮ Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets ⋮ Improved worst-case complexity for the MIN 3-SET COVERING problem ⋮ Variable neighborhood search for the vertex separation problem ⋮ Colorings with few colors: counting, enumeration and combinatorial bounds ⋮ Determining the circular flow number of a cubic graph ⋮ A refined algorithm for maximum independent set in degree-4 graphs ⋮ Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem ⋮ An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs ⋮ An exact algorithm for maximum independent set in degree-5 graphs ⋮ A faster polynomial-space algorithm for Max 2-CSP ⋮ Linear-programming design and analysis of fast algorithms for Max 2-CSP ⋮ Fast algorithms for max independent set ⋮ The \textsc{max quasi-independent set} problem ⋮ The many facets of upper domination ⋮ Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem} ⋮ A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP ⋮ Exact algorithms for exact satisfiability and number of perfect matchings ⋮ Finding a dominating set on bipartite graphs ⋮ Unnamed Item ⋮ Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds ⋮ Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems ⋮ Finding and counting permutations via CSPs ⋮ On two techniques of combining branching and treewidth ⋮ Faster graph coloring in polynomial space ⋮ Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3 ⋮ Algorithmic Aspects of Upper Domination: A Parameterised Perspective ⋮ Bounded-Degree Techniques Accelerate Some Parameterized Graph Algorithms ⋮ Improving TSP Tours Using Dynamic Programming over Tree Decompositions.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- New spectral lower bounds on the bisection width of graphs
- A partial k-arboretum of graphs with bounded treewidth
- The vertex separation and search number of a graph
- Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- Which problems have strongly exponential complexity?
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- A note on the complexity of minimum dominating set
- A \(2^{|E|/4}\)-time algorithm for MAX-CUT
- A new approach to proving upper bounds for MAX-2-SAT
- Graph minors. II. Algorithmic aspects of tree-width
- Finding a Maximum Independent Set
- Paths, Stars and the Number Three
- Algorithms and Computation
- STACS 2004
- Automata, Languages and Programming
- Graph-Theoretic Concepts in Computer Science
- Automata, Languages and Programming
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: Pathwidth of cubic graphs and exact algorithms
