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