A simple linear-time algorithm for finding path-decompositions of small width
Copyright policy )A simple linear-time algorithm for finding path-decompositions of small width
We described a simple algorithm running in linear time for each fixed constant $k$, that either establishes that the pathwidth of a graph $G$ is greater than $k$, or finds a path-decomposition of $G$ of width at most $O(2^{k})$. This provides a simple proof of the result by Bodlaender that many families of graphs of bounded pathwidth can be recognized in linear time.
9 pages
- University of Victoria Canada
- University of Victoria Canada
Analysis of algorithms and problem complexity, Combinatorial problems, Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), FOS: Mathematics, Mathematics - Combinatorics, Analysis of algorithms, Combinatorics (math.CO), 05c85 68q25, Algorithms
Analysis of algorithms and problem complexity, Combinatorial problems, Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), FOS: Mathematics, Mathematics - Combinatorics, Analysis of algorithms, Combinatorics (math.CO), 05c85 68q25, Algorithms
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).15 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!