Pathwidth of cubic graphs and exact algorithms

DOI10.1016/J.IPL.2005.10.012zbMATH Open1191.68826DBLPjournals/ipl/FominH06OpenAlexW2170702810WikidataQ56032469 ScholiaQ56032469MaRDI QIDQ1045933FDOQ1045933

Authors: Fedor V. Fomin, Kjartan Høie 

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

Recommendations

• Computing Pathwidth Faster Than 2 n
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• A bound on the pathwidth of sparse graphs with applications to exact algorithms
• scientific article; zbMATH DE number 176762
• Packing three-vertex paths in 2-connected cubic graphs.

zbMATH Keywords

treewidthexact exponential algorithmgraph algorithmspathwidthcubic graphmax-cutmaximum independent setminimum dominating set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Cites Work

• STACS 2004
• A partial k-arboretum of graphs with bounded treewidth
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Which problems have strongly exponential complexity?
• Automata, Languages and Programming
• Graph minors. II. Algorithmic aspects of tree-width
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Graph-Theoretic Concepts in Computer Science
• Paths, Stars and the Number Three
• The vertex separation and search number of a graph
• Finding a Maximum Independent Set
• A note on the complexity of minimum dominating set
• Title not available (Why is that?)
• Title not available (Why is that?)
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• A new approach to proving upper bounds for MAX-2-SAT
• Graph-Theoretic Concepts in Computer Science
• Title not available (Why is that?)
• Automata, Languages and Programming
• Title not available (Why is that?)
• New spectral lower bounds on the bisection width of graphs
• A \(2^{|E|/4}\)-time algorithm for MAX-CUT
• Algorithms and Computation

Cited In (40)

• Finding a dominating set on bipartite graphs
• The \textsc{max quasi-independent set} problem
• Improved edge-coloring with three colors
• A bisection approach to subcubic maximum induced matching
• Exact algorithms for exact satisfiability and number of perfect matchings
• Determining the circular flow number of a cubic graph
• Colorings with few colors: counting, enumeration and combinatorial bounds
• A faster polynomial-space algorithm for Max 2-CSP
• Bounded-degree techniques accelerate some parameterized graph algorithms
• On two techniques of combining branching and treewidth
• A refined algorithm for maximum independent set in degree-4 graphs
• Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems
• Exploiting sparsity for bipartite Hamiltonicity
• Title not available (Why is that?)
• Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
• Finding and counting permutations via CSPs
• Title not available (Why is that?)
• The path-distance-width of hypercubes
• Algorithmic aspects of \textsc{Upper Domination}: a parameterised perspective
• An exact algorithm for maximum independent set in degree-5 graphs
• Variable neighborhood search for the vertex separation problem
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width
• Fast algorithms for max independent set
• Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
• On the complexity of the approximation of nonplanarity parameters for cubic graphs
• Improved worst-case complexity for the MIN 3-SET COVERING problem
• Improving TSP tours using dynamic programming over tree decompositions
• 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
• Faster graph coloring in polynomial space
• Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets
• An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs
• Counting Maximal Independent Sets in Subcubic Graphs
• The many facets of upper domination
• A cubic algorithm for the directed Eulerian subgraph problem
• Colorings with few colors: counting, enumeration and combinatorial bounds
• Algorithms for solving problems on graphs of bounded pathwidth
• Title not available (Why is that?)

This page was built for publication: Pathwidth of cubic graphs and exact algorithms

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