Cover Image

A recursive linear time modular decomposition algorithm via LexBFS

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Corneil, Derek, Habib, Michel, Paul, Christophe, Tedder, Marc
Format:	Preprint
Published:	2007
Subjects:	Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Recoloring via modular decomposition
by: Belavadi, Manoj, et al.
Published: (2024)

Circle graphs can be recognized in linear time
by: Paul, Christophe, et al.
Published: (2025)

Tree-layout based graph classes: proper chordal graphs
by: Paul, Christophe, et al.
Published: (2022)

Complexity results on the decomposition of a digraph into directed linear forests and out-stars
by: Hörsch, Florian, et al.
Published: (2024)

Tree-partitions and small-spread tree-decompositions
by: Distel, Marc, et al.
Published: (2026)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
by: Korhonen, Tuukka, et al.
Published: (2024)

A linear-time algorithm for $(1+ε)Δ$-edge-coloring
by: Bernshteyn, Anton, et al.
Published: (2024)

A generic Branch-and-Cut algorithm for bi-objective binary linear programs
by: Fouilhoux, Pierre, et al.
Published: (2024)

Planar induced paths via a decomposition into non-crossing ordered graphs
by: Duron, Julien, et al.
Published: (2025)

Near-linear time subhypergraph counting in bounded degeneracy hypergraphs
by: Paul-Pena, Daniel, et al.
Published: (2025)

Antimagic Labeling of Graphs Using Prime Numbers
by: Islam, Arafat, et al.
Published: (2024)

Approximating temporal modularity on graphs of small underlying treewidth
by: Agdur, Vilhelm, et al.
Published: (2025)

A heuristic search algorithm for discovering large Condorcet domains
by: Zhou, Bei, et al.
Published: (2023)

Secure Domination in Bisplit graphs -- A Structural and algorithmic study
by: D, Swathi, et al.
Published: (2025)

An orderly algorithm for generation of Condorcet Domains
by: Zhou, Bei, et al.
Published: (2025)

Certified algorithms for numerical semigroups in Rocq
by: Bartoletti, Massimo, et al.
Published: (2025)

Extending Ghouila-Houri's Characterization of Comparability Graphs to Temporal Graphs
by: Charbit, Pierre, et al.
Published: (2025)

On coarse tree decompositions and coarse balanced separators
by: Abrishami, Tara, et al.
Published: (2025)

Tree decompositions with small width, spread, order and degree
by: Wood, David R.
Published: (2025)

Trade-off between spread and width for tree decompositions
by: Bodlaender, Hans L., et al.
Published: (2026)

Approximation algorithms for job scheduling with block-type conflict graphs
by: Furmańczyk, Hanna, et al.
Published: (2022)

Tree decompositions whose trees are subgraphs: An application of Simon's factorization
by: Bourneuf, Romain, et al.
Published: (2026)

An incremental exact algorithm for the hyper-rectangular clustering problem with axis-parallel clusters
by: Donne, Diego Delle, et al.
Published: (2024)

Conditional Separation as a Binary Relation. A Coq Assisted Proof
by: Chancelier, Jean-Philippe, et al.
Published: (2021)

Testing popularity in linear time via maximum matching
by: Bérczi-Kovács, Erika, et al.
Published: (2023)

Modeling energy collection with shortest paths in rectangular grids: an efficient algorithm for energy harvesting
by: Díaz-Bañez, José-Miguel, et al.
Published: (2025)

Elementary methods for splitting representations of Rook monoids: a gentle introduction to groupoids
by: Duchamp, Gérard Henry Edmond, et al.
Published: (2024)

Strongly k-recursive sequences
by: Krenn, Daniel, et al.
Published: (2024)

A verified implementation of the Misra and Gries edge coloring algorithm
by: Bhoja, Arohee
Published: (2025)

The Closed Geodetic Game: algorithms and strategies
by: Dailly, Antoine, et al.
Published: (2024)

Karp's patching algorithm on dense digraph
by: Frieze, Alan
Published: (2025)

Faster algorithms for graph homomorphism via tractable constraint satisfaction
by: Carbonnel, Clément
Published: (2026)

On the Vertices of Delta-modular Polyhedra
by: Mikhail, Bludov, et al.
Published: (2025)

Switched max-plus linear-dual inequalities: cycle time analysis and applications
by: Zorzenon, Davide, et al.
Published: (2023)

Bow Metrics and Hyperbolicity
by: Dragan, Feodor F., et al.
Published: (2024)

A Caro-Wei bound for induced linear forests in graphs
by: Joret, Gwenaël, et al.
Published: (2024)

Fast algorithm for $S$-packing coloring of Halin graphs
by: Zhang, Xin, et al.
Published: (2025)

ELECTRE TRI-nB, pseudo-disjunctive: axiomatic and combinatorial results
by: Bouyssou, Denis, et al.
Published: (2024)

Faster 3-colouring algorithm for graphs of diameter 3
by: Groenland, Carla, et al.
Published: (2026)

Odd coloring graphs with linear neighborhood complexity
by: Davies, James, et al.
Published: (2025)