An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph

Cited In (82)

Counting edge-injective homomorphisms and matchings on restricted graph classes
\(r\)-Dynamic chromatic number of some line graphs
New results and open problems in line graphs
Computation of Wiener polynomial and index of line subdivision friendship and line subdivision bifriendship graphs using Matlab program
The structure of (theta, pyramid, 1‐wheel, 3‐wheel)‐free graphs
Minimizing the Hamming distance between a graph and a line-graph to discover the topology of an electrical network
A dynamic algorithm for line graph recognition
Counting Weighted Independent Sets beyond the Permanent
Gorenstein and Cohen–Macaulay matching complexes
On the parameterized complexity of the acyclic matching problem
Edge intersection graphs of linear 3-uniform hypergraphs
Color-line and proper color-line graphs
Clique-perfectness of complements of line graphs
On minimal forbidden subgraph characterizations of balanced graphs
Line graphs with a Cohen-Macaulay or Gorenstein clique complex
Fair allocation of indivisible items with conflict graphs
On the monophonic rank of a graph
Matching cutsets in graphs
On an edge partition and root graphs of some classes of line graphs
Line graphs for a multiplex network
Clique coverings and claw-free graphs
On graphs with no induced subdivision of \(K_4\)
A reduction algorithm for the weighted stable set problem in claw-free graphs
A labeling algorithm to recognize a line digraph and output its root graph
On the iterated edge-biclique operator
Local Clique Covering of Claw-Free Graphs
Coloring perfect graphs with no balanced skew-partitions
The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
Recognising graphic and matroidal connectivity functions
Partial characterizations of coordinated graphs: Line graphs and complements of forests
Detecting strong cliques
Strong cliques in diamond-free graphs
The edge Hamiltonian path problem is NP-complete for bipartite graphs
Dominoes
Fixed cardinality stable sets
Decomposition by clique separators
Intersection graphs of paths in a tree
The complexity of dissociation set problems in graphs
On stable cutsets in line graphs
List monopolar partitions of claw-free graphs
On the hardness of recognizing triangular line graphs
Finding the root graph through minimum edge deletion
Biclique graphs and biclique matrices
Generalized line graphs: Cartesian products and complexity of recognition
A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
Line graphs of bounded clique-width
Independent point-set domination in line graphs
A search strategy for the elementary cycles of a directed graph
A polynomial characterization of some graph partitioning problems
Title not available (Why is that?)
Forests and trees among Gallai graphs
Decomposing Berge graphs and detecting balanced skew partitions
Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
Generalizations of line graphs and applications
On the Iterated Biclique Operator
A lower bound on the Hamiltonian path completion number of a line graph
Recognizing \(k\)-path graphs
The (theta, wheel)-free graphs. IV: Induced paths and cycles
Triangle packings and transversals of some \(K_{4}\)-free graphs
Reconstructing a graph from its arc incidence graph
Almost every graph is divergent under the biclique operator
Graphs vertex-partitionable into strong cliques
An upper bound for the chromatic number of line graphs
Degree distribution and assortativity in line graphs of complex networks
ILIGRA: an efficient inverse line graph algorithm
A linear algorithm for the Hamiltonian completion number of the line graph of a cactus.
An algorithm to recognize a middle graph
On the edges’ PageRank and line graphs
A finite characterization and recognition of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 in the class of threshold graphs
Basic perfect graphs and their extensions
Exact algorithms for maximum independent set
Combinatorial optimization with 2-joins
On the edge‐biclique graph and the iterated edge‐biclique operator
Clique-perfectness of complements of line graphs
Edge intersection graphs of linear 3-uniform hypergraphs
On stable cutsets in claw-free graphs and planar graphs
Characterization of common-edge sigraph
Fast recognition of doubled graphs
Two Hamiltonian cycles
Local search algorithms for finding the Hamiltonian completion number of line graphs
Biclique graphs of interval bigraphs

This page was built for publication: An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph

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