Intersection graphs of non-crossing paths

DOI10.1016/J.DISC.2023.113498MaRDI QIDQ6041577zbMATH OpenOpenAlexFDO

Authors Steven Chaplick

Publication date 31 May 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.disc.2023.113498

zbMATH Keywords

dominating setsHamiltonian cyclesclique treesnon-crossing modelsminimum-leaf spanning trees

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)

Recommendations

• scientific article; zbMATH DE number 3912430
• Intersection graphs of vertex disjoint paths in a tree
• Recognition algorithm for intersection graphs of edge disjoint paths in a tree
• scientific article; zbMATH DE number 4116559
• A faster algorithm to recognize undirected path graphs

Cites work

• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 1496855 (Why is no real title available?)
• scientific article; zbMATH DE number 7080199 (Why is no real title available?)
• A characterisation of rigid circuit graphs
• A faster algorithm to recognize undirected path graphs
• A note on the Hamiltonian circuit problem on directed path graphs
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• A recognition algorithm for the intersection graphs of paths in trees
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithmic graph theory and perfect graphs
• An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
• Boundary classes for graph problems involving non-local properties
• Characterizations of strongly chordal graphs
• Characterizing path graphs by forbidden induced subgraphs
• Claw-free graphs---a survey
• Clique tree generalization and new subclasses of chordal graphs
• Clustering and domination in perfect graphs
• Combinatorial problems on \(H\)-graphs
• Computing a minimum outer-connected dominating set for the class of chordal graphs
• Computing role assignments of proper interval graphs in polynomial time
• Dominating Sets in Chordal Graphs
• Edge Dominating Sets in Graphs
• Finding Hamiltonian circuits in proper interval graphs
• Finding and counting small induced subgraphs efficiently
• Finding four-node subgraphs in triangle time
• From path graphs to directed path graphs
• HAMILTONian circuits in chordal bipartite graphs
• Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor
• Incidence matrices and interval graphs
• Independent domination in chordal graphs
• Intersection graphs of Helly families of subtrees
• Intersection graphs of non-crossing paths
• Intersection graphs of paths in a tree
• Kernelization of graph Hamiltonicity: proper \(H\)-graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• On \(H\)-topological intersection graphs
• On domination and independent domination numbers of a graph
• On nontransitive indifference
• On the complexity of fixed parameter clique and dominating set
• On the tractability of optimization problems on \(H\)-graphs
• Representation of a finite graph by a set of intervals on the real line
• Representations of chordal graphs as subtrees of a tree
• Sphere and dot product representations of graphs
• Steiner trees, connected domination and strongly chordal graphs
• The LBFS structure and recognition of interval graphs
• The clique-separator graph for chordal graphs
• The edge Hamiltonian path problem is NP-complete for bipartite graphs
• The forbidden subgraph characterization of directed vertex graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Topics in Intersection Graph Theory
• U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
• Which problems have strongly exponential complexity?

Cited in

(2)

• Routes enumeration in a Boolean with respect to intersection and nonintersection relations
• Intersection graphs of non-crossing paths

This page was built for publication: Intersection graphs of non-crossing paths

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