REVIEW 3 cited by
A recursive linear time modular decomposition algorithm via LexBFS
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original abstract
A module of a graph G is a set of vertices that have the same set of neighbours outside. Modules of a graphs form a so-called partitive family and thereby can be represented by a unique tree MD(G), called the modular decomposition tree. Motivated by the central role of modules in numerous algorithmic graph theory questions, the problem of efficiently computing MD(G) has been investigated since the early 70's. To date the best algorithms run in linear time but are all rather complicated. By combining previous algorithmic paradigms developed for the problem, we are able to present a simpler linear-time that relies on very simple data-structures, namely slice decomposition and sequences of rooted ordered trees.
Forward citations
Cited by 3 Pith papers
-
Distance Vector Domination
The paper proves that Vector Domination is W[1]-hard when parameterized by neighborhood diversity, and gives fixed-parameter algorithms for Distance Vector Domination under modular-width and treewidth parameters.
-
Towards the Recognition of Oriented Interval Graphs
Two constrained recognition problems for oriented interval graphs are solved in linear time, improving a prior quadratic algorithm and solving the proper/unit case.
-
Parameterized Complexity of (d,r)-Domination via Modular Decomposition
The authors prove that (d,r)-domination is fixed-parameter tractable by modular-width plus demand, admits polynomial compressions by modular-width and iterated type partition number plus demand, and admits a polynomia...
Discussion (0). Continue with ORCID to comment.