Michel Habib

Orcid: 0000-0002-8564-2314

Affiliations:
  • University Paris Diderot, France


According to our database1, Michel Habib authored at least 134 papers between 1979 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
\(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs.
SIAM J. Discret. Math., March, 2024

Subquadratic-time Algorithm for the Diameter and all Eccentricities on Median Graphs.
Theory Comput. Syst., February, 2024

2023
A new graph parameter to measure linearity.
J. Graph Theory, July, 2023

Diagnosability for a family of matching composition networks.
J. Supercomput., May, 2023

Pattern detection in ordered graphs.
CoRR, 2023

Forbidden Patterns in Temporal Graphs Resulting from Encounters in a Corridor.
Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2023

2022
A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs.
Theor. Comput. Sci., 2022

Connectivity for some families of composition networks.
Theor. Comput. Sci., 2022

Diameter, Eccentricities and Distance Oracle Computations on <i>H</i>-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik-Chervonenkis Dimension.
SIAM J. Comput., 2022

Guiding Random Walks by Effective Resistance for Effective Node Embedding.
Proceedings of the Pattern Recognition and Artificial Intelligence, 2022

2021
Graph Classes and Forbidden Patterns on Three Vertices.
SIAM J. Discret. Math., 2021

Corrigendum: LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs.
SIAM J. Comput., 2021

Fast Diameter Computation within Split Graphs.
Discret. Math. Theor. Comput. Sci., 2021

Classifying grounded intersection graphs via ordered forbidden patterns.
CoRR, 2021

Diameter, radius and all eccentricities in linear time for constant-dimension median graphs.
CoRR, 2021

(α, β)-Modules in Graphs.
CoRR, 2021

Diameter in linear time for constant-dimension median graphs.
Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium, 2021

2020
Maximum Induced Matching Algorithms via Vertex Ordering Characterizations.
Algorithmica, 2020

Diameter computation on <i>H</i>-minor free graphs and graphs of bounded (distance) VC-dimension.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Approximating Modular Decomposition Is Hard.
Proceedings of the Algorithms and Discrete Applied Mathematics, 2020

2019
When an optimal dominating set with given constraints exists.
Theor. Comput. Sci., 2019

Fast approximation of eccentricities and distances in hyperbolic graphs.
J. Graph Algorithms Appl., 2019

Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension.
CoRR, 2019

A General Algorithmic Scheme for Modular Decompositions of Hypergraphs and Applications.
Proceedings of the Combinatorial Algorithms - 30th International Workshop, 2019

2018
Representation of lattices via set-colored posets.
Discret. Appl. Math., 2018

Revisiting Radius, Diameter, and all Eccentricity Computation in Graphs through Certificates.
CoRR, 2018

Fast Approximation of Centrality and Distances in Hyperbolic Graphs.
Proceedings of the Combinatorial Optimization and Applications, 2018

2017
A new LBFS-based algorithm for cocomparability graph recognition.
Discret. Appl. Math., 2017

Towards A Unified View of Linear Structure on Graph Classes.
CoRR, 2017

2016
Unified View of Graph Searching and LDFS-Based Certifying Algorithms.
Encyclopedia of Algorithms, 2016

On the Power of Graph Searching for Cocomparability Graphs.
SIAM J. Discret. Math., 2016

Preface.
RAIRO Oper. Res., 2016

A tie-break model for graph search.
Discret. Appl. Math., 2016

Algorithmic aspects of switch cographs.
Discret. Appl. Math., 2016

Read networks and k-laminar graphs.
CoRR, 2016

Maximal cliques structure for cocomparability graphs and applications.
CoRR, 2016

2015
Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs: With an application to the six degrees of separation games.
Theor. Comput. Sci., 2015

Into the Square: On the Complexity of Some Quadratic-time Solvable Problems.
Proceedings of the 16th Italian Conference on Theoretical Computer Science, 2015

A tie-break model for graph search.
CoRR, 2015

2014
Influence of the tie-break rule on the end-vertex problem.
Discret. Math. Theor. Comput. Sci., 2014

Into the Square - On the Complexity of Quadratic-Time Solvable Problems.
CoRR, 2014

Computing H-Joins with Application to 2-Modular Decomposition.
Algorithmica, 2014

Colored Modular and Split Decompositions of Graphs with Applications to Trigraphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2014

On the Solvability of the Six Degrees of Kevin Bacon Game - A Faster Graph Diameter and Radius Computation Method.
Proceedings of the Fun with Algorithms - 7th International Conference, 2014

2013
Unique perfect phylogeny is intractable.
Theor. Comput. Sci., 2013

On computing the diameter of real-world undirected graphs.
Theor. Comput. Sci., 2013

LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs.
SIAM J. Comput., 2013

The Arboreal Jump Number of an Order.
Order, 2013

A general method for common intervals.
CoRR, 2013

2012
Detecting 2-joins faster.
J. Discrete Algorithms, 2012

Constructing a Minimum phylogenetic Network from a Dense triplet Set.
J. Bioinform. Comput. Biol., 2012

Reduced clique graphs of chordal graphs.
Eur. J. Comb., 2012

Tree-representation of set families and applications to combinatorial decompositions.
Eur. J. Comb., 2012

Polynomial-time recognition of clique-width ≤3 graphs.
Discret. Appl. Math., 2012

Additive Spanners and Distance and Routing Labeling Schemes for Hyperbolic Graphs.
Algorithmica, 2012

Algorithms for Some H-Join Decompositions.
Proceedings of the LATIN 2012: Theoretical Informatics, 2012

2011
Complexity issues for the sandwich homogeneous set problem.
Discret. Appl. Math., 2011

On a conjecture of compatibility of multi-states characters
CoRR, 2011

On a Conjecture about Compatibility of Multi-states Characters.
Proceedings of the Algorithms in Bioinformatics - 11th International Workshop, 2011

Unique Perfect Phylogeny Is <i>NP</i>-Hard.
Proceedings of the Combinatorial Pattern Matching - 22nd Annual Symposium, 2011

2010
A survey of the algorithmic aspects of modular decomposition.
Comput. Sci. Rev., 2010

Structure and Recognition of 3,4-leaf Powers of Galled Phylogenetic Networks in Polynomial Time
CoRR, 2010

Unique perfect phylogeny is NP-hard
CoRR, 2010

2009
A Decomposition Theorem for Chordal Graphs and its Applications.
Electron. Notes Discret. Math., 2009

Linear Algorithms for Chordal Graphs of Bounded Directed Vertex Leafage.
Electron. Notes Discret. Math., 2009

On some simplicial elimination schemes for chordal graphs.
Electron. Notes Discret. Math., 2009

Unifying the representation of symmetric crossing families and weakly partitive families.
Electron. Notes Discret. Math., 2009

Algorithmic aspects of a general modular decomposition theory.
Discret. Appl. Math., 2009

Polynomial-Time Algorithm for the Leafage of Chordal Graphs.
Proceedings of the Algorithms, 2009

Level-k Phylogenetic Networks Are Constructable from a Dense Triplet Set in Polynomial Time.
Proceedings of the Combinatorial Pattern Matching, 20th Annual Symposium, 2009

Diameter and Center Computations in Networks.
Proceedings of the 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2009

2008
Competitive graph searches.
Theor. Comput. Sci., 2008

A Simple Linear Time LexBFS Cograph Recognition Algorithm.
SIAM J. Discret. Math., 2008

Fast computation of empirically tight bounds for the diameter of massive graphs.
ACM J. Exp. Algorithmics, 2008

A note on computing set overlap classes.
Inf. Process. Lett., 2008

Notes on diameters, centers, and approximating trees of delta-hyperbolic geodesic spaces and graphs.
Electron. Notes Discret. Math., 2008

A Representation Theorem for Union-Difference Families and Application.
Proceedings of the LATIN 2008: Theoretical Informatics, 2008

Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs.
Proceedings of the 24th ACM Symposium on Computational Geometry, 2008

2007
On transitive orientations with restricted covering graphs.
Inf. Process. Lett., 2007

Can transitive orientation make sandwich problems easier?
Discret. Math., 2007

Simple, linear-time modular decomposition
CoRR, 2007

Unifying Two Graph Decompositions with Modular Decomposition.
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

2006
Foreword.
Theory Comput. Syst., 2006

On Modular Decomposition Concepts: the case for Homogeneous Relations.
Electron. Notes Discret. Math., 2006

Algorithmic Aspects of a Novel Modular Decomposition Theory
CoRR, 2006

Homogeneity vs. Adjacency: Generalising Some Graph Decomposition Algorithms.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2006

2005
The number of Moore families on <i>n</i>=6.
Discret. Math., 2005

A simple linear time algorithm for cograph recognition.
Discret. Appl. Math., 2005

Revisiting T. Uno and M. Yagiura's Algorithm .
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

2004
Computational aspects of the 2-dimension of partially ordered sets.
Theor. Comput. Sci., 2004

Bimodular Decomposition of Bipartite Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2004

A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension.
Proceedings of the Algorithm Theory, 2004

Maximal Common Connected Sets of Interval Graphs.
Proceedings of the Combinatorial Pattern Matching, 15th Annual Symposium, 2004

2003
A note on finding all homogeneous set sandwiches.
Inf. Process. Lett., 2003

2002
Graph Decompositions andFactorizing Permutations.
Discret. Math. Theor. Comput. Sci., 2002

The perception of stop consonant sequences in dyslexic and normal children.
Proceedings of the 7th International Conference on Spoken Language Processing, ICSLP2002, 2002

2001
A simple paradigm for graph recognition: application to cographs and distance hereditary graphs.
Theor. Comput. Sci., 2001

Linear time recognition of P4-indifference graphs.
Discret. Math. Theor. Comput. Sci., 2001

Efficient algorithms on distributive lattices.
Discret. Appl. Math., 2001

Diameter determination on restricted graph families.
Discret. Appl. Math., 2001

2000
Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing.
Theor. Comput. Sci., 2000

Polynomial Time Recognition of Clique-Width \le \leq 3 Graphs (Extended Abstract).
Proceedings of the LATIN 2000: Theoretical Informatics, 2000

1999
Partition Refinement Techniques: An Interesting Algorithmic Tool Kit.
Int. J. Found. Comput. Sci., 1999

Encoding of Multiple Inheritance Hierarchies and Partial Orders.
Comput. Intell., 1999

1998
Diameter Determination on Restricted Graph Faminlies.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1998

A Synthesis on Partition Refinement: A Useful Routine for Strings, Graphs, Boolean Matrices and Automata.
Proceedings of the STACS 98, 1998

Representation of stereochemistry using combinatorial maps.
Proceedings of the Discrete Mathematical Chemistry, 1998

1997
Preface: Orders, Algorithms and Applications.
Theor. Comput. Sci., 1997

Gray Codes for the Ideals of Interval Orders.
J. Algorithms, 1997

Graph decompositions and factorizing permutations.
Proceedings of the Fifth Israel Symposium on Theory of Computing and Systems, 1997

1996
Tree Structure for Distributive Lattices and its Applications.
Theor. Comput. Sci., 1996

1995
A Linear Algorithm To Decompose Inheritance Graphs Into Modules.
Algorithmica, 1995

Chordal Graphs and Their Clique Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1995

1994
On the Interplay Between Interval Dimension and Dimension.
SIAM J. Discret. Math., 1994

Bit-Vector Encoding for Partially Ordered Sets.
Proceedings of the Orders, 1994

Proposal for a Monotonic Multiple Inheritance Linearization.
Proceedings of the Ninth Annual Conference on Object-Oriented Programming Systems, 1994

A New Linear Algorithm for Modular Decomposition.
Proceedings of the Trees in Algebra and Programming, 1994

1993
On the calculation of transitive reduction - closure of orders.
Discret. Math., 1993

1992
An Efficient Algorithm to Recognize Prime Undirected Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1992

Monotonic Conflict Resolution Mechanisms for Inheritance.
Proceedings of the Seventh Annual Conference on Object-Oriented Programming Systems, 1992

1991
Interval dimension is a comparability invariant.
Discret. Math., 1991

1990
Remarks on Some Concurrency Measures.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1990

1987
On some complexity properties of N-free posets and posets with bounded decomposition diameter.
Discret. Math., 1987

On Some Algorithms for Multiple Inheritance in Object-Oriented Programming.
Proceedings of the ECOOP'87 European Conference on Object-Oriented Programming, 1987

1986
CABRI, An Interactive System for Graph Manipulation.
Proceedings of the Graphtheoretic Concepts in Computer Science, International Workshop, 1986

1985
1-Intersecting families.
Discret. Math., 1985

N-free posets as generalizations of series-parallel posets.
Discret. Appl. Math., 1985

1984
On linear k-arboricity.
Discret. Math., 1984

Jump number of dags having Dilworth number 2.
Discret. Appl. Math., 1984

1982
Some problems about linear arboricity.
Discret. Math., 1982

1981
Partitive hypergraphs.
Discret. Math., 1981

1979
Nombre de sauts et graphes série-parallèles.
RAIRO Theor. Informatics Appl., 1979

On the X-join decomposition for undirected graphs.
Discret. Appl. Math., 1979


  Loading...