Random Generation and Enumeration of Proper Interval Graphs
From MaRDI portal
Publication:3605496
DOI10.1007/978-3-642-00202-1_16zbMath1211.68291OpenAlexW1483146092MaRDI QIDQ3605496
Katsuhisa Yamanaka, Toshiki Saitoh, Ryuhei Uehara, Masashi Kiyomi
Publication date: 24 February 2009
Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-00202-1_16
Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs, Binary bubble languages and cool-lex order
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear time recognition algorithm for proper interval graphs
- Finding Hamiltonian circuits in proper interval graphs
- The NP-completeness of the bandwidth minimization problem
- A short proof that `proper = unit'
- Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
- Efficient generation of plane trees.
- Algorithmic graph theory and perfect graphs
- Reverse search for enumeration
- A bijection between realizers of maximal plane graphs and pairs of non-crossing Dyck paths
- A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
- Succinct Representation of Balanced Parentheses and Static Trees
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- The bandwidth problem for graphs and matrices—a survey
- A Linear Time Algorithm for Deciding Interval Graph Isomorphism
- Graph Classes: A Survey
- A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
- Combinatorial Pattern Matching
- Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
- A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
- Graph-Theoretic Concepts in Computer Science
