NDLI: Enlarging Directed Graphs To Ensure All Nodes Are Contained In Cycles

Please wait, while we are loading the content...

A Critical Discourse Analysis of Governance Issues Affecting Public Private Partnership Contracting for Information Systems Implementations: A South African Case Study

On the prioritization of data quality challenges in e-health systems in South Africa

N-Gram Representations For Comment Filtering

Theorising inter-organisational health information systems as complex adaptive systems in the context of emergency medical services

Towards an Extensible Generic Agent-Based Simulator for Mammals

An XSet Based Protocol for Coordinating the Behaviour of Stigmergic Ant-Like Robotic Devices

CAPP: A C++ Aspect-Oriented Based Framework for Parallel Programming with OpenCL

Contributor Motivation in Online Knowledge Sharing Communities with Reputation Management Systems

Managing Globally Distributed Software Development Projects using Virtual Teams: A Middle East Case Study

Commercial Brain Computer Interface: Potential as a Natural User Interface

Use of the Alice visual environment in teaching and learning object-oriented programming

Using character valence in computer generated music to produce variation aligned to a storyline

Evolving Game Playing Strategies for Othello Incorporating Reinforcement Learning and Mobility

Violent gaming and player aggression: Exploring the effects of socio-psychological and technology influences

SpotMal: A hybrid malware detection framework with privacy protection for BYOD

The use of Facebook by a Community Policing Forum to combat crime

Using Business Intelligence to Support Strategic Sustainability Information Management

Evaluating an Artifact in Design Science Research

A system dynamics approach to increasing user participation in a blog-based online social network: The case of Bonfiire

Edit Distance-based Digraph Similarity

Toward a framework for ontology modularity

Organisational Barriers to Including Web Data in Traditional BI Practice

Towards a Smartphone User Competency Evolution Model

Challenges to the Organisational Adoption of Big Data Analytics: A Case Study in the South African Telecommunications Industry

Metrics for the Case Management Modeling and Notation (CMMN) Specification

Evaluating Resolution-Based Reasoning Heuristics for Connection Tableau

An Ontology for Tuberculosis Treatment Adherence Behaviour

Maps as a technique for visualizing load-shedding schedules

The User Experience Landscape of South Africa

Developing a Conceptual Model for Facilitating the Issuing of Digital Badges in a Resource Constrained Environment

SPLicing TABASCO: Custom-Tailored Software Product Line Variants from Taxonomy-Based Toolkits

Genetic Algorithms as a feasible re-planning mechanism for Belief-Desire-Intention Agents

Design Guidelines for Business Intelligence Tools for Novice Users

Blinkered Views of Out-Group Mobile Phone Usage: Moving Towards Less Stereotyping of "Others"

Comparison of effectiveness of two mobile application designs for encouraging children to read

eModeration: Towards a User Experience Evaluation Framework

Clustering in 1D Binary Elementary Cellular Automata

Enlarging Directed Graphs To Ensure All Nodes Are Contained In Cycles

Using technology to gain knowledge: Development, implementation and evaluation of a mobile digital skills curriculum for educators

Classification of Heuristics for Components of e-Learning

Enlarging Directed Graphs To Ensure All Nodes Are Contained In Cycles

Content Provider	ACM Digital Library
Author	Sanders, I. D. van der Linde, J. J.
Abstract	Many algorithms in graph theory add or remove either edges or nodes (or both) to solve a given problem. Graph augmentation typically concerns the addition of edges to a graph to satisfy some connectivity property of the graph. This paper focuses on the addition of vertices to a graph to satisfy a specific connectivity property: ensuring that all the nodes of the graph are contained within cycles. A distinction is made between graph augmentation (edge addition), and graph enlargement (vertex addition). The particular problem addressed here is the enlarging of a digraph which is an abstraction defined in the "shoe matching problem" and represents people who require different sizes of shoes. To be able to satisfy all of the participants, every node (person) in the digraph must be contained in at least one cycle. This paper looks at ways to improve on the original approach to graph enlargment. It redefines the cost model used in the original work, presents three improvements to the original approach and shows that these approaches do indeed offer benefits in terms of the number of nodes needed to solve the problem and/or the speed of enlargement.
Starting Page	1
Ending Page	10
Page Count	10
File Format	PDF
ISBN	9781450336833
DOI	10.1145/2815782.2815825
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-09-28
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Directed graphs Cycle picking Graph enlargement
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Cooperating to buy shoes in the real world: online cycle picking in directed graphs

Cooperating to buy shoes: an application of picking cycles in directed graphs

Even Cycles in Directed Graphs

Edge-Disjoint Cycles in Regular Directed Graphs (2000)

On the Number of Cycles in a Graph with Restricted Cycle Lengths

Finding shortest non-trivial cycles in directed graphs on surfaces

Edge-disjoint cycles in regular directed graphs

Moore graphs and cycles are extremal graphs for convex cycles (2012).

Edge-disjoint cycles in regular directed graphs

Enlarging Directed Graphs To Ensure All Nodes Are Contained In Cycles

Similar Documents

Cooperating to buy shoes in the real world: online cycle picking in directed graphs

Cooperating to buy shoes: an application of picking cycles in directed graphs

Even Cycles in Directed Graphs

Edge-Disjoint Cycles in Regular Directed Graphs (2000)

On the Number of Cycles in a Graph with Restricted Cycle Lengths

Finding shortest non-trivial cycles in directed graphs on surfaces

Edge-disjoint cycles in regular directed graphs

Moore graphs and cycles are extremal graphs for convex cycles (2012).

Edge-disjoint cycles in regular directed graphs

Enlarging Directed Graphs To Ensure All Nodes Are Contained In Cycles