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

Cited in

(88)

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

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)