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

Cited in

(88)

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

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)